We could serialize a tree in any DFS order (inorder, preorder or postorder) and then deserialize tree. The only important thing is to mark the necessary None node.
In this solution, we use preorder as the DFS order.
# 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
"""
ans = []
self._dfs(root, ans)
ans = [str(i) for i in ans]
return ', '.join(ans)
def deserialize(self, data):
"""Decodes your encoded data to tree.
:type data: str
:rtype: TreeNode
"""
tmp = data.split(', ')
values = []
for v in tmp:
if v == 'None':
values.append(None)
else:
values.append(int(v))
return self._dfs_recover(values[::-1])
def _dfs(self, node, ans):
if node is None:
ans.append(None)
return
ans.append(node.val)
self._dfs(node.left, ans)
self._dfs(node.right, ans)
def _dfs_recover(self, values):
if not values:
return None
v = values.pop()
if v is None:
return None
node = TreeNode(v)
node.left = self._dfs_recover(values)
node.right = self._dfs_recover(values)
return node
# Your Codec object will be instantiated and called as such:
# codec = Codec()
# codec.deserialize(codec.serialize(root))