297. Serialize and Deserialize Binary Tree - cocoder39/coco39_LC GitHub Wiki
297. Serialize and Deserialize Binary Tree
use pre-order traversal to serialize so you can deserialize the tree easily
SEPARATOR = ','
NONE_NODE = '#'
class Codec:
def serialize(self, root: TreeNode) -> str:
"""Encodes a tree to a single string.
:type root: TreeNode
:rtype: str
"""
return SEPARATOR.join(self.encode(root))
def encode(self, root: TreeNode) -> list:
if not root:
return [NONE_NODE]
res = [str(root.val)]
res.extend(self.encode(root.left))
res.extend(self.encode(root.right))
return res
def deserialize(self, data):
"""Decodes your encoded data to tree.
:type data: str
:rtype: TreeNode
"""
vals = iter(data.split(SEPARATOR))
return self.decode(vals)
def decode(self, iterator: Iterator[str]) -> TreeNode:
val = next(iterator)
if val == NONE_NODE:
return None
node = TreeNode(int(val))
node.left = self.decode(iterator)
node.right = self.decode(iterator)
return node
class Codec:
def serialize(self, root: TreeNode) -> str:
"""Encodes a tree to a single string.
:type root: TreeNode
:rtype: str
1 2 # # 3 4 5 # #
"""
if not root:
return ''
data = []
self.serializeHelper(root, data)
return ','.join(data)
def serializeHelper(self, root: TreeNode, data: List[str]) -> None:
if not root:
data.append('#')
else:
data.append(str(root.val))
self.serializeHelper(root.left, data)
self.serializeHelper(root.right, data)
def deserialize(self, data: str):
"""Decodes your encoded data to tree.
:type data: str
:rtype: TreeNode
"""
if not data:
return None
tokens = data.split(',')
tokens.reverse()
return self.deserializeHelper(tokens)
def deserializeHelper(self, tokens: List[str]) -> TreeNode:
val = tokens[-1]
tokens.pop()
if val == '#':
return None
root = TreeNode(int(val))
root.left = self.deserializeHelper(tokens)
root.right = self.deserializeHelper(tokens)
return root
===============================================================================
Main idea is to use preorder to encode bst, thus can easily distinguish root, left, right. better than using bfs to traversal level by level. time is O(n)
1
/ \
2 3
/ \
4 5
1 2 # # 3 4 # # 5 # #
class Codec {
public:
// Encodes a tree to a single string.
string serialize(TreeNode* root) {
string res;
serialize(root, res);
cout << res << endl;
return res;
}
// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
istringstream in(data);
return deserialize(in);
}
private:
void serialize(TreeNode* root, string& res) {
if (! root) {
res += "# ";
return;
}
res += to_string(root->val) + " ";
serialize(root->left, res);
serialize(root->right, res);
}
TreeNode* deserialize(istringstream& in) {
string token;
in >> token;
if (token == "#") {
return nullptr;
}
TreeNode* node = new TreeNode(stoi(token));
node->left = deserialize(in); //recursion until visiting '#'
node->right = deserialize(in);
return node;
}
};
second round
class Codec {
public:
// Encodes a tree to a single string.
string serialize(TreeNode* root) {
if (! root) {
return "# ";
} else {
return to_string(root->val) + " " + serialize(root->left) + serialize(root->right);
}
}
// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
istringstream iss(data);
return helper(iss);
}
private:
TreeNode* helper(istringstream& iss) {
string token;
iss >> token;
if (token == "#") {
return nullptr;
} else {
TreeNode* root = new TreeNode(stoi(token));
root->left = helper(iss);
root->right = helper(iss);
return root;
}
}
};
follow up: serialize a trie use dfs to serialize trie, making it easy to deserialize. dfs is an extension of preorder
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Aug. 16, 2020 Option 1: pre-order traversal - recursion easy to implement
def serialize(self, root):
"""Encodes a tree to a single string.
:type root: TreeNode
:rtype: str
"""
def helper(node):
if node is None:
data.append('#')
else:
data.append(str(node.val))
helper(node.left)
helper(node.right)
data = []
helper(root)
return ",".join(data)
def deserialize(self, data):
"""Decodes your encoded data to tree.
:type data: str
:rtype: TreeNode
"""
iterator = iter(data.split(','))
return self.formNode(iterator)
def formNode(self, iterator):
val = next(iterator)
if val == '#':
return None
node = TreeNode(int(val))
node.left = self.formNode(iterator)
node.right = self.formNode(iterator)
return node
Option 2: pre-order traversal - DFS with stack pitfall: need to append '#' after while loop. Eg, root is None, or last None has been popped out from stack
def serialize(self, root):
"""Encodes a tree to a single string.
:type root: TreeNode
:rtype: str
"""
node = root
stack = []
data = []
while node or len(stack) > 0:
if node:
data.append(str(node.val))
stack.append(node.right)
node = node.left
else:
data.append('#')
node = stack.pop()
data.append('#')
return ",".join(data)
def deserialize(self, data):
"""Decodes your encoded data to tree.
:type data: str
:rtype: TreeNode
"""
iterator = iter(data.split(','))
return self.formNode(iterator)
def formNode(self, iterator):
val = next(iterator)
if val == '#':
return None
node = TreeNode(int(val))
node.left = self.formNode(iterator)
node.right = self.formNode(iterator)
return node
Option 3: pre-order traversal - queue
def serialize(self, root):
"""Encodes a tree to a single string.
:type root: TreeNode
:rtype: str
"""
queue = collections.deque()
queue.append(root)
data = []
while queue:
node = queue.popleft()
if node:
data.append(str(node.val))
queue.append(node.left)
queue.append(node.right)
else:
data.append('#')
return ','.join(data)
def deserialize(self, data):
"""Decodes your encoded data to tree.
:type data: str
:rtype: TreeNode
"""
iterator = iter(data.split(','))
val = next(iterator)
if val == '#':
return None
queue = collections.deque()
root = TreeNode(int(val))
queue.append(root)
while queue:
node = queue.popleft()
left_val = next(iterator)
if left_val != '#':
node.left = TreeNode(int(left_val))
queue.append(node.left)
else:
node.left = None
right_val = next(iterator)
if right_val != '#':
node.right = TreeNode(int(right_val))
queue.append(node.right)
else:
node.right = None
return root