Serialize and Deserialize Binary Tree

Problem Id: 297 Difficulty: Hard Tag: Tree Tag: Design


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':
        return self._dfs_recover(values[::-1])

    def _dfs(self, node, ans):
        if node is None:

        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))