Serialize and Deserialize BST

Problem Id: 449 Difficulty: Medium Tag: Tree


Intuition

With the preorder of a Binary Serach Tree, we could recover this tree. So we could use the preorder as the serrialization of the BST and then recover from it.

Solution


# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Codec:

    def serialize(self, root: TreeNode) -> str:
        """Encodes a tree to a single string.
        """
        if root is None:
            return ''
        preorder = []
        self._preorder(root, preorder)
        return ' '.join([str(i) for i in preorder])

    def _preorder(self, node, preorder):
        if node is None:
            return
        preorder.append(node.val)
        self._preorder(node.left, preorder)
        self._preorder(node.right, preorder)

    def deserialize(self, data: str) -> TreeNode:
        """Decodes your encoded data to tree.
        """
        if not data:
            return None
        preorder = [int(i) for i in data.split(' ')]
        preorder_reverse = preorder[::-1]
        return self._helper(preorder_reverse)

    def _helper(self, preorder_reverse, hi=float('inf'), lo=float('-inf')):
        if not preorder_reverse:
            return None
        elif not lo < preorder_reverse[-1] < hi:
            return None
        node = TreeNode(preorder_reverse.pop())
        node.left = self._helper(preorder_reverse, node.val, lo)
        node.right = self._helper(preorder_reverse, hi, node.val)
        return node