297. Serialize and Deserialize Binary Tree

Design an algorithm and write code to serialize and deserialize a binary tree. Writing the tree to a file is called 'serialization' and reading back from the file to reconstruct the exact same binary tree is 'deserialization'.

Example

Example 1:

Input：{3,9,20,#,#,15,7}
Output：{3,9,20,#,#,15,7}
Explanation：
Binary tree {3,9,20,#,#,15,7},  denote the following structure:
   3
  / \
 9  20
   /  \
  15   7
it will be serialized {3,9,20,#,#,15,7}

Example 2:

Input：{1,2,3}
Output：{1,2,3}
Explanation：
Binary tree {1,2,3},  denote the following structure:
   1
  / \
 2   3
it will be serialized {1,2,3}

Our data serialization uses BFS traversal. This is just for when you got a Wrong Answer and want to debug the input.

Note: Do not use class member/global/static variables to store states. Your serialize and deserialize algorithms should be stateless.

1. /** 
2.  * Definition for a binary tree node. 
3.  * struct TreeNode { 
4.  *     int val; 
5.  *     TreeNode *left; 
6.  *     TreeNode *right; 
7.  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} 
8.  * }; 
9.  */  
10. class Codec {  
11. public:  
12.   
13.     // Encodes a tree to a single string.  
14.     string serialize(TreeNode* root) {  
15.         if (root == NULL) return "";  
16.           
17.         queue<TreeNode*> q;  
18.         q.push(root);  
19.           
20.         string result = "";  
21.         while (!q.empty()) {  
22.             TreeNode *curr = q.front();  
23.             q.pop();  
24.               
25.             if (!result.empty()) result += ",";  
26.             if (curr == NULL) {  
27.                 result += "#";  
28.                 continue;  
29.             }  
30.               
31.             result += to_string(curr->val);  
32.             q.push(curr->left);  
33.             q.push(curr->right);  
34.         }  
35.           
36.         return result;  
37.     }  
38.   
39.     // Decodes your encoded data to tree.  
40.     TreeNode* deserialize(string data) {  
41.         if (data.empty()) return NULL;  
42.           
43.         vector<string> ds = split(data, ",");  
44.         TreeNode *root = new TreeNode(stoi(ds[0]));  
45.           
46.         queue<TreeNode*> q;  
47.         q.push(root);  
48.           
49.         bool isRight = false;  
50.         for (int i = 1; i < ds.size(); i++) {  
51.             if (ds[i] != "#") {  
52.                 TreeNode *node = new TreeNode(stoi(ds[i]));  
53.                 if (isRight) {  
54.                     q.front()->right = node;  
55.                 } else {  
56.                     q.front()->left = node;  
57.                 }  
58.                 q.push(node);  
59.             }  
60.               
61.             if (isRight) q.pop();  
62.             isRight = !isRight;  
63.         }  
64.           
65.         return root;  
66.     }  
67.       
68.     vector<string> split(const string &data, string separator) {  
69.         vector<string> result;  
70.           
71.         int index, lastIndex = 0;  
72.         while ((index = data.find(separator, lastIndex)) != string::npos) {  
73.             result.push_back(data.substr(lastIndex, index - lastIndex));  
74.             lastIndex = index + separator.length();  
75.         }  
76.           
77.         if (lastIndex != data.length()) result.push_back(data.substr(lastIndex));  
78.           
79.         return result;  
80.     }  
81. };  

C++ does not have a split function.