LeetCode 449 - 序列化和反序列化二叉搜索树

摘要

「序列化和反序列化二叉搜索树」这道题，表面上是在考二叉树，其实真正的考点在于：你有没有真正理解 BST（Binary Search Tree）的性质。

如果把它当成普通二叉树去做，确实可以用层序遍历，加上null占位来解决，但那样字符串会很长，也完全没有利用 BST 的特性。而题目特意强调了一句：

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

这其实是在暗示：
BST 是可以只靠遍历顺序恢复出来的。

这篇文章会从实际业务场景聊起，解释为什么 BST 可以被“无损压缩”，再一步步带你用 Swift 写出一套简洁、高效、可运行的解法。

描述

题目要求我们设计一套算法，用来：

• 把一棵二叉搜索树序列化成字符串
• 再从这个字符串中反序列化，恢复成原来的 BST

有几个关键限制条件：

1. 输入保证一定是一棵 BST
2. 节点值范围是合法整数
3. 节点数量最多 10⁴
4. 序列化字符串要尽量紧凑

BST 有一个非常重要的性质：

• 左子树所有节点值 < 根节点
• 右子树所有节点值 > 根节点

这条规则，是我们能“少存信息、还能完整还原”的关键。

题解答案（核心思路）

为什么普通二叉树和 BST 不一样？

如果是普通二叉树，你只存前序遍历是没法还原结构的，比如：

1 \ 2

和

1 / 2

前序遍历都是[1,2]，结构信息丢失了。

但 BST 不一样。

BST 的关键点

只要你知道：

• 遍历顺序（比如前序）
• BST 的大小关系规则

那么不用存 null，也能恢复结构。

本题采用的策略

1. 序列化

   • 使用前序遍历（root → left → right）
   • 只记录节点值
   • 用逗号拼成字符串

2. 反序列化

   • 根据 BST 的区间规则递归构建
   • 每个节点值都必须落在合法区间(min, max)内
   • 一次遍历即可还原整棵树

这样做的好处是：

• 字符串非常紧凑
• 时间和空间效率都很高
• 思路清晰，代码不复杂

题解代码（Swift 可运行 Demo）

下面是完整可运行的 Swift 示例，包括TreeNode定义和测试代码。

importFoundationpublicclassTreeNode{publicvarval:Intpublicvarleft:TreeNode?publicvarright:TreeNode?publicinit(_val:Int){self.val=valself.left=nilself.right=nil}}classCodec{// MARK: - Serializefuncserialize(_root:TreeNode?)->String{varresult:[String]=[]funcpreorder(_node:TreeNode?){guardletnode=nodeelse{return}result.append(String(node.val))preorder(node.left)preorder(node.right)}preorder(root)returnresult.joined(separator:",")}// MARK: - Deserializefuncdeserialize(_data:String)->TreeNode?{ifdata.isEmpty{returnnil}varvalues=data.split(separator:",").map{Int($0)!}varindex=0funcbuild(_min:Int,_max:Int)->TreeNode?{ifindex>=values.count{returnnil}letval=values[index]ifval<min||val>max{returnnil}index+=1letnode=TreeNode(val)node.left=build(min,val)node.right=build(val,max)returnnode}returnbuild(Int.min,Int.max)}}

题解代码分析

1. 为什么用前序遍历？

前序遍历的第一个节点一定是根节点，这对构建树非常友好。

BST 的前序遍历有一个隐含规律：

• 一段连续小于 root 的值，一定属于左子树
• 后面大于 root 的值，一定属于右子树

结合区间限制，我们就能精准判断一个值“该不该被消费”。

2. serialize 的核心逻辑

funcpreorder(_node:TreeNode?){guardletnode=nodeelse{return}result.append(String(node.val))preorder(node.left)preorder(node.right)}

这里非常直接：

• 不存 null
• 不加多余符号
• 单纯记录节点值

这也是字符串“足够紧凑”的关键原因。

3. deserialize 的核心逻辑

funcbuild(_min:Int,_max:Int)->TreeNode?

这是整个算法的精髓。

含义是：

• 当前子树中，合法节点值必须在(min, max)区间内
• 如果当前值不在区间内，说明它属于别的子树，直接返回 nil
• 如果合法，就创建节点，并递归构建左右子树

因为index是全局递增的，所以每个节点只会被处理一次。

4. 为什么不需要回退 index？

这是很多人一开始想不通的点。

原因在于：

• 前序遍历是严格的「根 → 左 → 右」
• 一旦某个值不在当前区间，它一定属于后续的右子树或祖先节点
• 所以不能消费，就不动 index

这是 BST 性质带来的好处。

示例测试及结果

我们用示例一来跑一遍：

letcodec=Codec()letroot=TreeNode(2)root.left=TreeNode(1)root.right=TreeNode(3)letdata=codec.serialize(root)print("序列化结果:",data)letnewRoot=codec.deserialize(data)print("反序列化完成，根节点:",newRoot?.val??-1)

输出结果：

序列化结果: 2,1,3 反序列化完成，根节点: 2

对于空树：

print(codec.serialize(nil))// ""print(codec.deserialize("")==nil)// true

结果也是符合预期的。

时间复杂度

• 序列化：每个节点访问一次，O(n)
• 反序列化：每个节点构建一次，O(n)

总体时间复杂度：O(n)

空间复杂度

• 序列化字符串占 O(n)
• 递归调用栈最坏 O(n)（退化成链表）

总体空间复杂度：O(n)

总结

LeetCode 449 是一道非常经典的「理解型」题目。

它并不难写，但非常考察你是否真正理解了：

• BST 的结构特性
• 遍历顺序和树结构之间的关系
• 如何用“约束条件”减少冗余数据