标签: 树 深度优先搜索 广度优先搜索 设计 二叉搜索树 字符串 二叉树
难度: Medium
序列化是将数据结构或对象转换为一系列位的过程，以便它可以存储在文件或内存缓冲区中，或通过网络连接链路传输，以便稍后在同一个或另一个计算机环境中重建。
设计一个算法来序列化和反序列化 二叉搜索树 。 对序列化/反序列化算法的工作方式没有限制。 您只需确保二叉搜索树可以序列化为字符串，并且可以将该字符串反序列化为最初的二叉搜索树。
编码的字符串应尽可能紧凑。
示例 1：
输入：root = [2,1,3] 输出：[2,1,3]
示例 2：
输入：root = [] 输出：[]
提示：
[0, 104]0 <= Node.val <= 104运行时间: 80 ms
内存: 19.7 MB
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Codec:
def __init__(self):
self.vals = []
def serialize(self, root: Optional[TreeNode]) -> str:
"""Encodes a tree to a single string.
"""
self.dfs1(root)
return ",".join(self.vals)
def dfs1(self, root):
if root is None:
return
self.vals.append(str(root.val))
self.dfs1(root.left)
self.dfs1(root.right)
def deserialize(self, data: str) -> Optional[TreeNode]:
"""Decodes your encoded data to tree.
"""
if data == "":
return
vals = [int(x) for x in data.split(",")]
return self.helper(vals, 0, len(vals)-1)
def helper(self, vals, i, j):
if i > j:
return
val = vals[i]
root = TreeNode(val)
k = i+1
while k <= j and vals[k] <= val:
k += 1
root.left = self.helper(vals, i+1, k-1)
root.right = self.helper(vals, k, j)
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
该题解使用深度优先搜索进行序列化和反序列化。序列化时，按照先根节点、然后左子树、最后右子树的顺序递归遍历二叉搜索树，将节点值存储到一个列表中。最后将列表转换为以逗号分隔的字符串。反序列化时，先将字符串按逗号分隔得到节点值列表，然后使用递归辅助函数重建二叉搜索树。递归函数根据当前子数组的起始和结束索引，找到第一个大于根节点值的位置 k，然后递归构建左子树（范围是 i+1 到 k-1）和右子树（范围是 k 到 j）。
时间复杂度: O(n^2)
空间复杂度: O(n)
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Codec:
def __init__(self):
self.vals = []
def serialize(self, root: Optional[TreeNode]) -> str:
"""
Encodes a tree to a single string.
"""
self.dfs1(root)
return ",".join(self.vals)
def dfs1(self, root):
"""
Performs a pre-order traversal of the BST and stores node values in a list.
"""
if root is None:
return
self.vals.append(str(root.val))
self.dfs1(root.left)
self.dfs1(root.right)
def deserialize(self, data: str) -> Optional[TreeNode]:
"""
Decodes your encoded data to tree.
"""
if data == "":
return
vals = [int(x) for x in data.split(",")]
return self.helper(vals, 0, len(vals)-1)
def helper(self, vals, i, j):
"""
Recursively reconstructs the BST from the serialized node values.
"""
if i > j:
return
val = vals[i]
root = TreeNode(val)
k = i+1
while k <= j and vals[k] <= val:
k += 1
root.left = self.helper(vals, i+1, k-1)
root.right = self.helper(vals, k, j)
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
先序遍历（根左右）在序列化和反序列化二叉搜索树时非常有用，因为先序遍历首先访问根节点，这使得在反序列化过程中可以直接从序列的开始重新构建出原始树的结构。使用中序遍历（左根右）序列化虽然仍然可以保持二叉搜索树的顺序，但在反序列化时无法直接确定根节点，因此需要额外的信息才能重建树。后序遍历（左右根）虽然最后访问根节点，可以从后往前构建树，但相较于先序遍历的直观和便捷性较差。
在该题解的实现中，并没有特别考虑重复值的情况，因为标准的二叉搜索树定义不包括重复元素。序列化和反序列化的过程假设了所有节点值是唯一的。如果实际应用中树可能包含重复值，则需要调整算法以适应重复值的处理，例如通过标记每个节点在树中的具体位置或者在序列化数据中添加额外的信息。
在此题解中，由于使用先序遍历和二叉搜索树的特性，序列化时没有存储空子树的特殊标记也足以确保反序列化的准确性。因为每个节点值的范围都受到它在树结构中位置的限制，即使没有空子树的特殊标记，仍可以通过当前节点值的范围来确定子树的边界。不过，对于一般的二叉树，不存储空节点信息可能会导致无法正确重建所有结构，特别是那些不平衡的部分。
当前实现中的方法确实需要在每次递归时扫描数组以找到右子树的起始位置，这在某些情况下可能效率较低（时间复杂度接近O(n^2)）。更优的方法是使用二分搜索技术或者额外的数据结构（如栈）来辅助定位，这可以显著提高效率。例如，可以在遍历数组时使用栈来跟踪潜在的右子节点，或者在二叉搜索树的性质基础上使用二分查找来确定元素分界，从而将时间复杂度降低到O(n log n)。