Serialize And Deserialize Binary Tree Problem
Description
LeetCode Problem 297.
Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.
Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.
Clarification: The input/output format is the same as how LeetCode serializes a binary tree. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.
Example 1:
1
2
Input: root = [1,2,3,null,null,4,5]
Output: [1,2,3,null,null,4,5]
Example 2:
1
2
Input: root = []
Output: []
Example 3:
1
2
Input: root = [1]
Output: [1]
Example 4:
1
2
Input: root = [1,2]
Output: [1,2]
Constraints:
- The number of nodes in the tree is in the range [0, 10^4].
- -1000 <= Node.val <= 1000
Sample C++ Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Codec {
public:
// Encodes a tree to a single string.
string serialize(TreeNode* root) {
string rootS, leftS, rightS;
if (root == NULL)
return "null";
queue<TreeNode*> bfsQ;
bfsQ.push(root);
rootS = to_string(root->val);
int len;
TreeNode* curr;
while (!bfsQ.empty()) {
len = bfsQ.size();
for (int i = 0; i < bfsQ.size(); i ++) {
curr = bfsQ.front();
bfsQ.pop();
if (curr != NULL) {
if (curr->left == NULL)
rootS += ",null";
else
rootS += "," + to_string(curr->left->val);
if (curr->right == NULL)
rootS += ",null";
else
rootS += "," + to_string(curr->right->val);
bfsQ.push(curr->left);
bfsQ.push(curr->right);
}
}
}
int l = rootS.size();
while ((l > 5) && (rootS.substr(l - 5, 5) == ",null")) {
rootS = rootS.substr(0, l - 5);
l = rootS.size();
}
return rootS;
}
string getNode(string& s) {
int i = 0;
string node;
while ((s[i] != ',') && (i < s.size())) {
node += s[i];
i ++;
}
if (i < s.size())
s = s.substr(i + 1, s.size() - i - 1);
else
s = "";
return node;
}
// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
if (data == "null")
return NULL;
string nodeS;
TreeNode* root = new TreeNode;
nodeS = getNode(data);
root->val = stoi(nodeS);
queue<TreeNode*> bfsQ;
bfsQ.push(root);
int len;
TreeNode* curr;
while (!bfsQ.empty()) {
len = bfsQ.size();
for (int i = 0;i < len; i ++) {
curr = bfsQ.front();
bfsQ.pop();
if (curr != NULL) {
nodeS = getNode(data);
if (nodeS.empty())
return root;
TreeNode* leftNode = new TreeNode;
leftNode->left = NULL;
leftNode->right = NULL;
if (nodeS == "null")
leftNode = NULL;
else
leftNode->val = stoi(nodeS);
curr->left = leftNode;
nodeS = getNode(data);
if (nodeS.empty())
return root;
TreeNode* rightNode = new TreeNode;
rightNode->left = NULL;
rightNode->right = NULL;
if (nodeS == "null")
rightNode = NULL;
else
rightNode->val = stoi(nodeS);
curr->right = rightNode;
bfsQ.push(leftNode);
bfsQ.push(rightNode);
}
}
}
return root;
}
};
// Your Codec object will be instantiated and called as such:
// Codec codec;
// codec.deserialize(codec.serialize(root));