Serialize and Deserialize Binary Tree

Intuition

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.

Solution


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