LeetCode: 449. Serialize and Deserialize BST

题目

原题地址:https://leetcode.com/problems/serialize-and-deserialize-bst/

Serialization is converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary search tree. There is no restriction on how your serialization/deserialization algorithm should work. You need to ensure that a binary search tree can be serialized to a string, and this string can be deserialized to the original tree structure.

The encoded string should be as compact as possible.

Example 1:

Input: root = [2,1,3]
Output: [2,1,3]

Example 2:

Input: root = []
Output: []

Constraints:

  • The number of nodes in the tree is in the range [0, 10^4].
  • 0 <= Node.val <= 10^4
  • The input tree is guaranteed to be a binary search tree.

题目大意是,设计一个类实现序列化和反序列化一个 BST 的功能

解法

序列化,中序遍历将节点的值用空格分隔组成一个字符串:

  • [1,null,2] 将序列化为 1 2
  • [2,1,3] 将序列化为 2 1 3
  • [5,3,6,2,4,null,7] 将序列化为 5 3 2 4 6 7

反序列化,按空格读取字符串中包含的所有节点的值,然后基于读取处理的值列表重建 BST:

  • 按照中序遍历的过程来重建 BST
  • 因为没有一个标识位标明哪里是空节点,所以需要在构建 BST 的时候 判断当前值是否符合假设的节点位置,比如, 预期当前值是左子树的 root 节点值,但是实际上它的值比 root 节点的值大, 说明 root 节点其实没有左子树, 预期当前值是右子树的 root 节点值,但是实际上它的值比 root 节点的值小, 说明 root 节点其实没有右子树,

这个思路的 Python 代码类似下面这样:

# 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):
        if root is None:
            return ''

        val = '{}'.format(root.val)
        if root.left is not None:
            val = '{} {}'.format(val, self.serialize(root.left))
        if root.right is not None:
            val = '{} {}'.format(val, self.serialize(root.right))

        return val

    def deserialize(self, data):
        """Decodes your encoded data to tree.
        """
        values = data.split()
        root = self._build_bst(values, -1, 10**4 + 1)
        return root

    def _build_bst(self, values, should_gt, should_lt):
        if not values:
            return None

        next_value = int(values[0])
        # 不是预期的左侧节点或右侧节点,说明这个位置应该为空
        if next_value <= should_gt or next_value >= should_lt:
            return None

        val = int(values.pop(0))
        root = TreeNode(val)
        # 左子树的值应当小于 root 节点的值
        root.left = self._build_bst(values, should_gt, val)
        # 右子树的值应当大于 root 节点的值
        root.right = self._build_bst(values, val, should_lt)

        return root


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

Comments