449. 序列化和反序列化二叉搜索树

Difficulty

Medium

Tags

二叉树

二叉搜索树

URL

https://leetcode-cn.com/problems/serialize-and-deserialize-bst/

Star

序列化是将数据结构或对象转换为一系列位的过程，以便它可以存储在文件或内存缓冲区中，或通过网络连接链路传输，以便稍后在同一个或另一个计算机环境中重建。

设计一个算法来序列化和反序列化 二叉搜索树 。对序列化/反序列化算法的工作方式没有限制。您只需确保二叉搜索树可以序列化为字符串，并且可以将该字符串反序列化为最初的二叉搜索树。

编码的字符串应尽可能紧凑。

示例 1：


输入：root = [2,1,3]
输出：[2,1,3]

示例 2：


输入：root = []
输出：[]

提示：

树中节点数范围是 [0, 104]

0 <= Node.val <= 104

题目数据保证输入的树是一棵二叉搜索树。

注意：不要使用类成员/全局/静态变量来存储状态。你的序列化和反序列化算法应该是无状态的。

法1 递归

思路

参考

在297题目中，序列化的时候，将空节点也存进去用来判断递归是否应该返回上一层。然不同于297题，本题是二叉搜索树，所以可以利用二叉搜索树的性质。在二叉搜索树中，左子树一定小于当前节点，右子树一定大于当前节点，所以对于前序遍历的序列化字符串

根节点是首个子字符串代表的数字，右子树是首个大于根节点之后的字符串

图解

对如下二叉搜索树

前序遍历后的节点顺序如下：

从该图便可清晰的判断每棵树根节点，左子节点、右子节点

题解


# 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 ""
				# 防止多余的逗号
        res = str(root.val)
        if root.left:
            res += "," + self.serialize(root.left)
        if root.right:
            res += "," + self.serialize(root.right)
        return res        

    def deserialize(self, data: str) -> TreeNode:
        """Decodes your encoded data to tree.
        """
        if len(data) == 0:
            return None
        data = data.split(",")

        return self.dfs(data, -float("inf"), float("inf"))
    
    def dfs(self, data, min_val, max_val):
        if len(data) == 0:
            return None
        # 先不弹出来，判断是否合法
        cur_val = int(data[0])
        if cur_val > max_val or cur_val < min_val:
            return None
        # 合法，弹出来
        cur_val = int(data.pop(0))
        cur_node = TreeNode(cur_val)
        cur_node.left = self.dfs(data, min_val, cur_val)
        cur_node.right = self.dfs(data, cur_val, max_val)

        return cur_node

# 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