297 Serialize and Deserialize Binary Tree
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.
For example, you may serialize the following tree
1
/ \
2 3
/ \
4 5
as "[1,2,3,null,null,4,5]", just the same as how LeetCode OJ serializes a binary tree. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.
- Note: Do not use class member/global/static variables to store states. Your serialize and deserialize algorithms should be stateless.
Notes
Serialize
Traverse the tree in level-order, note several details.- (1) The NULL left-child and NULL right-child also has to be output here;
- (2) Don't have to output an "all-NULL" level (last level).
- (3) For each level, output the node in this level; record all its child node to a temparory vector; repeat it while the temparory vector is not "all=NULL".
Deserialize
Convert the input string to a list of strings.- the sublte treatment of the last element!
- Traverse the deserialize output, construct the tree level by level.
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Codec:
def serialize(self, root):
"""Encodes a tree to a single string.
:type root: TreeNode
:rtype: str
"""
if ( root == None ): return "[]"
tmp1, tmp2 = [root], []
result = [str(root.val)]
while ( len(tmp1) != 0 ):
if ( tmp1[0].left != None ):
result.append(str(tmp1[0].left.val))
tmp2.append(tmp1[0].left)
else: result.append("null")
if ( tmp1[0].right != None ):
result.append(str(tmp1[0].right.val))
tmp2.append(tmp1[0].right)
else: result.append("null")
tmp1.pop(0)
if ( len(tmp1) == 0 ): tmp1, tmp2 = tmp2[:], tmp1[:]
i = len(result)-1
while ( result[i] == "null" ): i -= 1
s = "["
for j in range(i):
s += str(result[j])
s += ","
s += str(result[i])
s += "]"
return s
def deserialize(self, data):
"""Decodes your encoded data to tree.
:type data: str
:rtype: TreeNode
"""
if ( len(data) == 2 ): return None
i = 0
nums = []
integer = ""
while ( i <= len(data)-1 ):
if ( (data[i] <= "9" and data[i] >= "0" ) or data[i] == "-"):
integer += data[i]
if ( data[i] == "," ):
nums.append(integer)
integer = ""
if ( data[i] == "n" ):
nums.append("n")
i += 4
i += 1
if (integer != "" ): nums.append(integer)
root = TreeNode(int(nums[0]))
tmp1, tmp2 = [root], []
i = 1
while (len(tmp1) != 0 ):
if ( i >= len(nums) ): break
if ( nums[i] != "n" ):
tNode = TreeNode(int(nums[i]))
tmp1[0].left = tNode
tmp2.append(tNode)
i += 1
if ( i >= len(nums) ): break
if ( nums[i] != "n" ):
tNode = TreeNode(int(nums[i]))
tmp1[0].right = tNode
tmp2.append(tNode)
tmp1.pop(0)
if ( len(tmp1) == 0 ): tmp1, tmp2 = tmp2[:], tmp1[:]
i += 1
return root
# Your Codec object will be instantiated and called as such:
# codec = Codec()
# codec.deserialize(codec.serialize(root))
/**
* 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:
string join(vector<string>& list) {
string s = "[";
int n = list.size();
if ( n == 0 ) return "[]";
for ( int i = 0; i <= n-2; i++ ) s += list[i] + ",";
s += list[n-1] + "]";
return s;
}
vector<string> split(string s) {
int n = s.size();
vector<string> res;
string tmp = "";
int i = 1;
while ( i <= n-1 ) {
if ( (s[i] >= '0' and s[i] <= '9' ) or s[i] == '-' ) {tmp += s[i++]; continue;}
if ( s[i] == ',' or s[i] == ']') {
if (tmp.size() != 0 ){ res.push_back(tmp); tmp = "";}
i += 1;
continue;
}
if ( s[i] == 'n' ) {
res.push_back("null");
i += 5;
continue;
}
}
return res;
}
// Encodes a tree to a single string.
string serialize(TreeNode* root) {
// "[1,2,3,null,null,4,5]"
vector<string> res;
if ( root == NULL ) return join(res);
vector<TreeNode*> v1(1, root);
int tag = 0;
while ( v1.size() != 0 ) {
int n = v1.size();
vector<TreeNode*> v2;
for ( int i = 0; i <= n-1; i++ ) {
if ( v1[i] == NULL ) { res.push_back("null"); continue;}
res.push_back(to_string(v1[i]->val));
v2.push_back(v1[i]->left);
v2.push_back(v1[i]->right);
tag += ( v1[i]->left != NULL);
tag += ( v1[i]->right != NULL );
}
if ( tag == 0 ) break;
v1 = v2;
tag = 0;
}
return join(res);
}
// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
vector<string> str_list = split(data);
int n = str_list.size();
if ( n == 0 ) return NULL;
TreeNode* root = new TreeNode(atoi(str_list[0].c_str()));
vector<TreeNode*> v1(1, root);
int i = 1;
while ( i <= n-1 ) {
int n1 = v1.size(), j = 0;
vector<TreeNode*> v2;
while ( j <= n1-1 ) {
if ( i == n ) break;
TreeNode* tnode = v1[j];
if ( str_list[i] != "null" ) {
TreeNode* tmp = new TreeNode(atoi(str_list[i].c_str()));
tnode->left = tmp;
v2.push_back(tmp);
}
i += 1;
if ( i == n ) break;
if ( str_list[i] != "null" ){
TreeNode* tmp = new TreeNode(atoi(str_list[i].c_str()));
tnode->right = tmp;
v2.push_back(tmp);
}
i += 1;
j += 1;
}
if ( i == n ) break;
v1 = v2;
}
return root;
}
};
// Your Codec object will be instantiated and called as such:
// Codec codec;
// codec.deserialize(codec.serialize(root));