449.md

449. Serialize and Deserialize BST

Solution 1

# 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
        """
        ret = []
        def pre_order(root):
            if root:
                ret.append(root.val)
                pre_order(root.left)
                pre_order(root.right)
        pre_order(root)
        return " ".join(map(str, ret))

    def deserialize(self, data):
        """Decodes your encoded data to tree.
        
        :type data: str
        :rtype: TreeNode
        """
        vals = deque(map(int, data.split()))
        def build(min_val, max_val):
            if vals and min_val < vals[0] < max_val:
                cur_val = vals.popleft()
                node = TreeNode(cur_val)
                node.left = build(min_val, cur_val)
                node.right = build(cur_val, max_val)
                return node
            return None
        return build(-float("inf"), float("inf"))


# Your Codec object will be instantiated and called as such:
# ser = Codec()
# deser = Codec()
# tree = ser.serialize(root)
# ans = deser.deserialize(tree)
# return ans