LeetCode 449. 序列化和反序列化二叉搜索树
题目描述
题意分析
将二叉搜索树编码为尽可能紧凑的字符串，再从字符串恢复原来的节点值和结构。利用 BST 的左子树值小于根、右子树值大于根这一性质，可以只记录前序节点值，不必为每个空孩子写占位符。本文用空字符串表示空树。
解法：前序遍历加上下界恢复
核心思路
[!blue]
前序遍历按“根、左子树、右子树”输出，每棵子树的节点在序列中连续出现。普通二叉树仅凭这些值无法知道左右子树的边界，但 BST 的取值范围提供了结构约束：以
value为根，左边只能取更小的值，右边只能取更大的值。定义
build(lower, upper)恢复值必须落在开区间(lower, upper)内的子树，用共享下标index指向下一个未读取的值。序列耗尽时返回空；若下一个值不在当前范围，说明它不能作为这棵子树的根，当前子树为空，应交还给上层处理，不能推进下标。值合法时，先将它作为根并推进下标，再按前序顺序恢复左子树
(lower, value)和右子树(value, upper)。保留原有另一侧边界，才能同时满足所有祖先的限制，而不只是与直接父节点比较。对合法 BST 的前序序列，下一项若属于当前子树，就必然是它的根；孩子递归又使用相同规则，返回时正好消耗完整子树。因而左右子树能依次唯一恢复，不需要重复搜索分界位置，也不会把属于后续子树的值提前丢弃。
初始上下界必须严格覆盖题目值域。代码使用 64 位边界，并直接传递根值作为新的开区间端点，无需对根值做加一或减一。每次反序列化重新创建共享下标，解析过程只依赖当前字符串。
解题步骤
- 序列化时前序访问所有非空节点，用空格分隔节点值；空树不写任何内容。
- 反序列化空字符串时返回空树，否则分割字段，将
index初始化为 0。- 从覆盖所有合法值的开区间开始调用
build。- 下标到末尾或下一个值越界时返回空，保持下标不变。
- 值合法时消费当前字段、创建根节点，然后依次用收紧后的范围恢复左、右子树。
代码实现
public class Codec {
public String serialize(TreeNode root) {
StringBuilder sb = new StringBuilder();
preorder(root, sb);
return sb.toString().trim();
}
private void preorder(TreeNode node, StringBuilder sb) {
if (node == null) {
return;
}
sb.append(node.val).append(' ');
preorder(node.left, sb);
preorder(node.right, sb);
}
public TreeNode deserialize(String data) {
if (data == null || data.isEmpty()) {
return null;
}
String[] values = data.split(" ");
int[] index = new int[1];
return build(values, index, Long.MIN_VALUE, Long.MAX_VALUE);
}
private TreeNode build(String[] values, int[] index, long lower, long upper) {
if (index[0] == values.length) {
return null;
}
int value = Integer.parseInt(values[index[0]]);
// 越界值属于其他子树，返回时不能消费它
if (value <= lower || value >= upper) {
return null;
}
// 合法根先消费，再让左右子树继续共享读取位置
index[0]++;
TreeNode node = new TreeNode(value);
node.left = build(values, index, lower, value);
node.right = build(values, index, value, upper);
return node;
}
}
import (
"strconv"
"strings"
)
type Codec struct {
}
func Constructor() Codec {
return Codec{}
}
func (this *Codec) serialize(root *TreeNode) string {
parts := []string{}
var preorder func(*TreeNode)
preorder = func(node *TreeNode) {
if node == nil {
return
}
parts = append(parts, strconv.Itoa(node.Val))
preorder(node.Left)
preorder(node.Right)
}
preorder(root)
return strings.Join(parts, " ")
}
func (this *Codec) deserialize(data string) *TreeNode {
if data == "" {
return nil
}
values := strings.Fields(data)
index := 0
var build func(int64, int64) *TreeNode
build = func(lower int64, upper int64) *TreeNode {
if index == len(values) {
return nil
}
value, _ := strconv.Atoi(values[index])
current := int64(value)
// 越界值属于其他子树，返回时不能消费它
if current <= lower || current >= upper {
return nil
}
// 合法根先消费，再让左右子树继续共享读取位置
index++
node := &TreeNode{Val: value}
node.Left = build(lower, current)
node.Right = build(current, upper)
return node
}
return build(-1<<63, 1<<63-1)
}
复杂度分析
- 时间复杂度：$O(n)$，其中 $n$ 是节点数。编码访问每个节点一次；解码时每个节点创建一次，并发起两次孩子调用，所以包含空子树判断在内的调用总数也是线性的。
- 空间复杂度：$O(n)$，编码字符串、解码分词和结果树都占线性空间；递归栈另外占 $O(h)$，其中 $h$ 为树高，树退化成链时为 $O(n)$。
关键点总结
[!green]
- 前序决定读取顺序，BST 的祖先上下界决定每个子树的范围，两者共同替代空节点标记。
- 只有成功创建节点时才推进下标，越界返回空不会丢弃尚未分配的值。
- 左右递归保留继承边界，始终满足整条祖先路径的 BST 约束。
易错点总结
[!yellow]
- 先递增下标再检查范围，会跳过属于其他子树的节点。
- 只比较父节点、丢掉原有另一侧边界，会把祖先另一分支的节点接到当前子树。
- 先恢复右子树会破坏前序的“根、左、右”读取顺序。
- 范围是开区间，初始边界不能等于某个合法节点值，否则这个值会被误判越界。
- 本方法依赖输入来自合法 BST 的前序编码，不能直接套用到普通二叉树的前序序列。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 297. 二叉树的序列化与反序列化 | 困难 | 普通二叉树需要保存空位结构，BST可利用值域上下界从前序序列还原。 |
| 255. 验证二叉搜索树的前序遍历序列 | 中等 | BST前序验证与还原都依赖进入右子树后的下界，本题还要实际创建节点。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！