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]"You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself
The Idea:
- The use of
ostringstreamandistringstreamallows us to cleanly delimit serialized words. - Serialization is pretty simply. We just continue to append to referenced string.
- Deserialization feeds in a referenced istream object which ensures that it will be read in linearly. The key in understand how it works is that we first build a stack of
TreeNode's in a pre-order fashion before connecting the tree together.
class Codec {
public:
// Encodes a tree to a single string.
string serialize(TreeNode* root) {
ostringstream os;
serialize(root, os);
return os.str();
}
// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
istringstream is(data);
return deserialize(is);
}
private:
void serialize(TreeNode* root, ostringstream &os) {
if (root) {
os << root->val << " ";
serialize(root->left, os);
serialize(root->right, os);
}
else os << "null ";
}
TreeNode* deserialize(istringstream &is) {
string cur_str;
is >> cur_str;
if (cur_str == "null") return nullptr;
TreeNode *temp = new TreeNode(stoi(cur_str));
temp->left = deserialize(is);
temp->right = deserialize(is);
return temp;
}
};
Python
# 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
"""
pre_order = []
def dfs(root):
if (root):
pre_order.append(str(root.val))
dfs(root.left)
dfs(root.right)
else:
pre_order.append('#')
dfs(root)
return ','.join(pre_order)
def deserialize(self, data):
"""Decodes your encoded data to tree.
:type data: str
:rtype: TreeNode
"""
data = data.split(',')
global_iter = [0]
def dfs(i):
if data[i[0]] == '#':
return None
else:
next_root = TreeNode(int(data[i[0]]))
i[0] += 1
next_root.left = dfs(i)
i[0] += 1
next_root.right = dfs(i)
return next_root
return dfs(global_iter)
# Your Codec object will be instantiated and called as such:
# codec = Codec()
# codec.deserialize(codec.serialize(root))
Last modified 4yr ago