8

LeetCode: 449. Serialize and Deserialize BST

 3 years ago
source link: https://mozillazg.com/2021/02/leetcode-449-serialize-and-deserialize-bst.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

题目

原题地址：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

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK