297. Serialize and Deserialize Binary Tree

01//Runtime: 452 ms, faster than 5.05% of C++ online submissions for Serialize and Deserialize Binary Tree.
02//Memory Usage: 38.7 MB, less than 41.53% of C++ online submissions for Serialize and Deserialize Binary Tree.
03/**
04 * Definition for a binary tree node.
05 * struct TreeNode {
06 *     int val;
07 *     TreeNode *left;
08 *     TreeNode *right;
09 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
10 * };
11 */
12
13class Codec {
14public:
15    template <typename Iter>
16    std::string join(Iter begin, Iter end, std::string const& separator)
17    {
18        std::ostringstream result;
19        result.precision(2); //for floating point
20        if (begin != end)
21            result << *begin++;
22        while (begin != end)
23            //std::fixed : for floating point
24            result << std::fixed << separator << *begin++;
25        return result.str();
26    }
27    
28    std::vector<std::string> string_split(std::string str, std::string delimiter){
29        size_t pos = 0;
30        std::string token;
31        std::vector<std::string> result;
32
33        //Style 2, can deal with all tokens inside the while loop
34        while(true){
35            pos = str.find(delimiter);
36            //works even if pos is string::npos
37            token = str.substr(0, pos);
38            result.push_back(token);
39            if(pos == string::npos) break;
40            //pos+1 equals to 0, so the line below can't handle this situation
41            str.erase(0, pos+delimiter.length());
42        }
43        return result;
44    }
45    
46    // Encodes a tree to a single string.
47    string serialize(TreeNode* root) {
48        vector<string> tokens;
49        
50        TreeNode* cur;
51        queue<TreeNode*> q;
52        q.push(root);
53        
54        while(!q.empty()){
55            cur = q.front(); q.pop();
56            
57            if(cur != nullptr){
58                tokens.push_back(to_string(cur->val));
59                //we also visit children who are nullptr
60                q.push(cur->left);
61                q.push(cur->right);
62            }else{
63                tokens.push_back("null");
64            }
65        }
66        
67        return join(tokens.begin(), tokens.end(), ",");
68    }
69
70    // Decodes your encoded data to tree.
71    TreeNode* deserialize(string data) {
72        vector<string> tokens = string_split(data, ",");
73        int n = tokens.size();
74        vector<TreeNode*> nodes(n);
75        
76        for(int i = 0; i < n; ++i){
77            if(tokens[i] == "null"){
78                nodes[i] = nullptr;
79            }else{
80                nodes[i] = new TreeNode(stoi(tokens[i]));
81            }
82        }
83        
84        //use bfs to reconstruct tree
85        TreeNode* cur;
86        int nodeCursor = 0;
87        queue<TreeNode*> q;
88        q.push(nodes[nodeCursor]);
89        
90        while(!q.empty()){
91            int levelSize = q.size();
92            
93            //visit level by level
94            while(levelSize-- > 0){
95                cur = q.front(); q.pop();
96                
97                if(cur != nullptr){
98                    cur->left = nodes[++nodeCursor];
99                    cur->right = nodes[++nodeCursor];
100                    
101                    q.push(cur->left);
102                    q.push(cur->right);
103                }
104            }
105        }
106        
107        return nodes[0];
108    }
109};
110
111// Your Codec object will be instantiated and called as such:
112// Codec codec;
113// codec.deserialize(codec.serialize(root));
114
115//recursion, preorder
116//https://leetcode.com/problems/serialize-and-deserialize-binary-tree/discuss/74253/Easy-to-understand-Java-Solution
117//Runtime: 624 ms, faster than 5.05% of C++ online submissions for Serialize and Deserialize Binary Tree.
118//Memory Usage: 38.2 MB, less than 42.14% of C++ online submissions for Serialize and Deserialize Binary Tree.
119class Codec {
120public:
121    void serial(TreeNode* node, string& str){
122        if(node == nullptr){
123            str += "null";
124        }else{
125            str += to_string(node->val) + ",";
126            serial(node->left, str); str += ",";
127            serial(node->right, str);
128        }
129    }
130    
131    // Encodes a tree to a single string.
132    string serialize(TreeNode* root) {
133        string str = "";
134        serial(root, str);
135        // cout << "str: " << str << endl;
136        return str;
137    }
138
139    std::vector<std::string> string_split(std::string str, std::string delimiter){
140        size_t pos = 0;
141        std::string token;
142        std::vector<std::string> result;
143
144        //Style 2, can deal with all tokens inside the while loop
145        while(true){
146            pos = str.find(delimiter);
147            //works even if pos is string::npos
148            token = str.substr(0, pos);
149            result.push_back(token);
150            if(pos == string::npos) break;
151            //pos+1 equals to 0, so the line below can't handle this situation
152            str.erase(0, pos+delimiter.length());
153        }
154        return result;
155    }
156    
157    TreeNode* deserial(queue<string>& q){
158        string token = q.front(); q.pop();
159        if(token == "null") return nullptr;
160        TreeNode* root = new TreeNode(stoi(token));
161        root->left = deserial(q);
162        root->right = deserial(q);
163        return root;
164    };
165    
166    // Decodes your encoded data to tree.
167    TreeNode* deserialize(string data) {
168        vector<string> tokens = string_split(data, ",");
169        queue<string, deque<string>> q(deque<string>(tokens.begin(), tokens.end()));
170        return deserial(q);
171    }
172};