LeetCode 449题是关于二叉搜索树（BST）的序列化和反序列化问题。序列化是将一个数据结构或对象状态转换为可存储或传输的格式的过程，以便在需要时可以恢复该数据结构或对象状态。反序列化是序列化的逆过程。
题目描述
你需要设计一个算法来实现二叉搜索树的序列化和反序列化。序列化是将一棵二叉搜索树转换为一个字符串，而反序列化是将一个字符串转换回一棵二叉搜索树。
要求
- 序列化和反序列化的算法应该是高效的，即时间复杂度和空间复杂度尽可能低。
- 序列化的结果应该是一个字符串，反序列化的输入也应该是一个字符串。
解决思路
由于二叉搜索树具有有序性，可以利用前序遍历和中序遍历的特性来进行序列化和反序列化。但更常见的方法是使用前序遍历结合null标记来进行序列化，这样可以简化反序列化的过程。
1. 序列化
使用前序遍历（根-左-右）来遍历树，并将每个节点的值转换为字符串，如果遇到null节点，则用特殊字符（如”#”）来表示。
2. 反序列化
将序列化后的字符串按前序遍历的顺序重新构建二叉搜索树。使用一个队列来存储节点值，逐个构建节点并按前序遍历的顺序连接左右子树。
代码实现（Python）
class TreeNode:
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.""" if not root: return ""
def preorder(node):
if not node:
return "# "
return str(node.val) + " " + preorder(node.left) + preorder(node.right)
return preorder(root)
def deserialize(self, data):
"""Decodes your encoded data to tree."""
if not data:
return None
def build_tree(values):
val = values.pop(0)
if val == "#":
return None
node = TreeNode(int(val))
node.left = build_tree(values)
node.right = build_tree(values)
return node
values = data.split()
return build_tree(values)Your Codec object will be instantiated and called as such:
ser = Codec()
deser = Codec()
tree = deser.deserialize(ser.serialize(root))
详细解释
-
序列化（serialize）:
- 使用递归函数
preorder进行前序遍历。 - 如果当前节点为null，返回”#”和一个空格。
- 否则，返回当前节点的值和一个空格，然后递归处理左子树和右子树。
- 使用递归函数
-
反序列化（deserialize）:
- 将输入的字符串按空格分割成列表
values。 - 使用递归函数
build_tree来构建树：- 从
values中取出第一个元素，如果是”#”，则返回None。 - 否则，创建一个新节点，递归构建其左子树和右子树。
- 从
- 将输入的字符串按空格分割成列表
复杂度分析
- 时间复杂度：序列化和反序列化均为O(n)，其中n是树中节点的数量。
- 空间复杂度：序列化使用O(h)的递归栈空间，反序列化使用O(n)的空间来存储节点值。
这种方法利用了二叉搜索树的性质和前序遍历的特性，实现了高效的序列化和反序列化。