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

2021-11-11 HGNULB 约 12 分钟

文章信息 8 个分类 7 个标签

分类

题目描述

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

题意分析

要设计一对互逆的方法：serialize 把一棵二叉搜索树压成字符串，deserialize 从这个字符串还原出结构完全相同的树。判题不比较字符串本身，只比较还原出来的树，所以编码格式可以自己定，唯一的硬性要求是信息不丢失。

题目特意强调「编码的字符串应尽可能紧凑」，这句话是整道题与 297 的分水岭。297 面对的是任意二叉树，结构信息必须显式写进字符串（通常是给每个空孩子留一个占位符）；而本题给的是二叉搜索树，左子树所有值严格小于根、右子树所有值严格大于根，这个约束本身就携带了结构信息，因此有机会把占位符全部省掉。看到「BST」和「紧凑」同时出现，就该往「用有序性替代显式分隔符」的方向想。

还有一条隐含约束：题目保证所有节点值互不相同。没有重复值，小于 和 大于 才能把每个值唯一地划归到某一侧，否则边界会出现歧义。

边界要盯住三处：空树必须能被序列化并原样还原，所以编码格式要留出「空串」这个合法取值；单节点树不能触发任何多余的分隔逻辑；节点值可以是负数，字符串切分不能依赖符号，只能靠空格之类的显式分隔符，同时值的范围可能顶到 32 位整数的两端，用来表示「无限制」的哨兵必须比它们更宽。

解法：前序遍历加上下界恢复

核心思路

先看最直接的做法：套用 297 的通用方案，前序遍历时把每个空孩子也写成一个 #。这样一定能还原，但一棵有 $n$ 个节点的二叉树有 $n + 1$ 个空指针，也就是说超过一半的 token 都是占位符，与「尽可能紧凑」的要求相悖。瓶颈就在这些占位符上。

于是问题变成：能不能只写 $n$ 个节点值，不写任何占位符，还原时靠别的信息判断「子树到此为止」？

关键观察分两层。第一层，前序序列的排布是有规律的：根排在最前，紧接着是左子树的全部节点，再接着是右子树的全部节点。所以还原时只要能定位「左子树在哪里结束」，递归就能继续。第二层，BST 的有序性恰好能给出这个分界：对根值 v 而言，紧随其后的一段连续 token 只要小于 v 就属于左子树，第一个大于 v 的 token 就是右子树的起点。

把这两层合起来，就得到了不需要占位符的还原方式：用一个全局游标按前序顺序读取 token，递归函数额外携带 (lower, upper) 表示当前这棵子树允许出现的值域开区间。读到游标处的值 v 时：

若 v 落在 (lower, upper) 内，说明它确实属于这棵子树，消耗掉它并建成根，然后递归构造左子树（值域收紧为 (lower, v)）和右子树（值域收紧为 (v, upper)）；

若 v 不在范围内，说明当前位置该是一棵空子树，返回 null 且不移动游标——这个值属于某一层祖先的右子树，要留给上层去读。

「不在范围内就不消耗 token」是整个算法的不变量所在。更精确地说，不变量是：每次调用 build(lower, upper) 返回时，游标恰好停在第一个不属于该子树的 token 上。这条不变量保证了每个 token 只被真正消耗一次，也保证了递归回到上层时接着往下读就是对的位置。

序列化端相应地只做一件事：按前序把节点值用空格拼起来，不写任何空节点标记。空树自然产出空串。

解题步骤

序列化用前序而不是中序：中序遍历 BST 得到的是升序序列，看似信息量足够，实则不然——升序序列丢失了树形，[1, 2, 3] 既可能来自以 2 为根的平衡树，也可能来自一条右斜链，还原不出原结构。前序把根放在最前，才能让递归「先定根、再分左右」。

用空格连接 token：节点值是多位数且可能带负号，不加分隔符会把 1 和 2 粘成 12。选空格是因为它不会与负号、数字冲突，切分时也最省事。

序列化空树返回空串：空树没有任何节点值，产出天然为空。反序列化端据此在最前面做一次空串判断，直接返回 null；不判的话切分空串会得到一个含空元素的数组，解析时抛异常。

反序列化用一个可共享的游标：Java 里传 int[] index 这样的单元素数组，Go 里用闭包捕获外层变量。必须是共享可变的——如果按值传 int，子递归里的推进不会反映到父调用，游标会在回溯时倒退，同一个 token 被反复读取导致死循环或结构错乱。

递归函数先判游标是否已到末尾：token 读完意味着树已建完，此时任何位置都该返回 null。不判会直接越界。

再判值是否落在 (lower, upper) 开区间内：写成 value <= lower || value >= upper 就返回 null。用开区间是因为 BST 值互不相同，等号出现即说明这个值属于别的子树。

确认合法后才推进游标、建节点：这两步的顺序不影响结果，但推进必须发生在两次递归调用之前，否则左子树会把根自己再读一遍。

左右子树的值域各收紧一侧：左子树传 (lower, value)，右子树传 (value, upper)。左子树保留下界、把上界压到根值，右子树保留上界、把下界抬到根值——祖先的约束必须一路继承下去，只压当前这一侧是不够的，否则右子树里会混进本该属于更上层的值。

根调用传入足够宽的哨兵：Java 用 Long.MIN_VALUE / Long.MAX_VALUE 并把参数声明为 long，Go 用 -1<<63 / 1<<63-1 并把比较值转成 int64。用 Integer.MIN_VALUE 作下界时，若树里真有一个值等于 Integer.MIN_VALUE，value <= lower 会误判成空子树。

以 BST [5, 3, 8, 2, 4, 7, 9]（根 5，左子树根 3 带孩子 2、4，右子树根 8 带孩子 7、9）走一遍。

序列化前序输出："5 3 2 4 8 7 9"。

反序列化从 build(-∞, +∞) 开始，游标 i = 0。读 5，落在范围内，消耗，i = 1，建根 5。
构造 5 的左子树 build(-∞, 5)：读 3，-∞ < 3 < 5 成立，消耗，i = 2，建节点 3。
　构造 3 的左子树 build(-∞, 3)：读 2，合法，消耗，i = 3，建节点 2。它的左子树 build(-∞, 2) 读到 4，4 >= 2 越界，返回 null 且游标不动；右子树 build(2, 3) 读到 4，4 >= 3 越界，同样返回 null。节点 2 完成，游标仍是 3。
　构造 3 的右子树 build(3, 5)：读 4，3 < 4 < 5 成立，消耗，i = 4，建节点 4。它的两个孩子调用读到 8，分别因 8 >= 4 和 8 >= 5 越界返回 null。
　节点 3 完成，返回，游标停在 4。
构造 5 的右子树 build(5, +∞)：读 8，合法，消耗，i = 5，建节点 8。
　8 的左子树 build(5, 8)：读 7，合法，消耗，i = 6，建节点 7，其两个孩子读到 9，因 9 >= 7、9 >= 8 越界返回 null。
　8 的右子树 build(8, +∞)：读 9，合法，消耗，i = 7，建节点 9，其两个孩子调用因游标到达末尾返回 null。
　节点 8 完成。

游标停在 7 即末尾，还原出的树与原树完全一致。整个过程中每个 token 恰好被消耗一次，越界判断共触发 8 次，对应原树的 8 个空指针，但它们一个字节都没写进字符串。

若把「越界返回 null」写成「越界也推进游标」：在 build(-∞, 2) 那一步读到 4 时游标就跳到 3，随后 3 的右子树读到的是 8 而不是 4，节点 4 永久丢失，还原出的树少一个节点。

代码实现

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;
    }
}

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)$，每个节点被访问一次并追加一次字符串；反序列化也是 $O(n)$，因为每个 token 至多被消耗一次，而「读了但越界返回」的次数等于空指针数，同样是 $O(n)$ 级别，两者相加仍是线性——注意这里不能因为「每层都要读一次 token」就误以为是 $O(n \log n)$，越界读取的总次数由树的空指针数封顶，与树高无关。

空间复杂度：$O(n)$。输出字符串与切分后的 token 数组都是 $n$ 量级；递归栈深度等于树高，平衡时为 $O(\log n)$、退化成链时为 $O(n)$，与前两项同阶。相比 297 的方案，本解省下的是常数因子——token 数从约 $2n + 1$ 降到 $n$，这正是题目所说的「紧凑」。

关键点总结

序列化题的通用判断是「结构信息从哪来」。任意二叉树只能把空指针显式写出来；一旦题目额外给了 BST、堆序、完全二叉树之类的性质，就该先问这个性质能否替代显式结构标记，这是从 297 迈向 449 的关键一步。

前序遍历天然把「根」放在段首，是所有「读一个值就能立刻建根、再分派左右」的还原算法的前提；中序虽然对 BST 更「自然」，却因为丢失了根的位置而无法单独还原结构。

用 (lower, upper) 值域约束替代分隔符，本质是把「这个 token 属不属于我」的判断从字符层面搬到了数值层面。同一套上下界技巧也用于 98 验证 BST，值得当成 BST 的标准工具记住。

递归中的游标必须是共享可变状态（数组包裹或闭包捕获），并且遵守「合法才推进、越界不推进」的不变量；面试时被追问「越界那次读取会不会把 token 弄丢」，能答出这条不变量就说明真的理解了。

面试里给出这一解法后，最好主动交代它与 297 通用解法的取舍：通用解法适用面更广、更好写，本解胜在紧凑且能展示对 BST 性质的运用。能说清「什么时候不该用」比只会写更受认可。

易错点总结

序列化改用中序遍历：BST [2, 1, 3] 与一条链 1 → 2 → 3（每个节点只有右孩子）中序输出都是 "1 2 3"，反序列化必然还原成同一棵树，其中一棵结构对不上。

反序列化时越界也推进游标：还原 "5 3 2 4 8 7 9"，在构造节点 2 的左孩子时读到 4 便把游标跳过，节点 4 再也不会被读到，还原出的树少了一个节点。

游标按值传参而不是共享：同样是 "5 3 2 4 8 7 9"，左子树里推进的游标回到父调用后归零，根 5 的右子树又从 token 3 开始读，直接建出一棵违反 BST 性质的树，甚至因为反复读取而无限递归。

右子树只传 (value, +∞) 而丢掉祖先上界：还原 "5 3 4 8" 这类序列时，节点 3 的右子树本应受上界 5 限制，若写成 (3, +∞)，8 会被错挂到 3 的右边，5 的右子树反而变空。

左子树传 (lower, upper) 忘了把上界压成 value：还原 "5 3 8"，构造 3 时上界仍是 +∞，8 被挂到 3 的右孩子上，5 的右子树为空，树形完全错位。

上下界用 int 且取 Integer.MIN_VALUE：树里若真有一个值等于 Integer.MIN_VALUE，根调用时 value <= lower 成立，直接返回 null，整棵树还原成空。

忘记判断空串：空树序列化得到 ""，Java 里 "".split(" ") 返回长度为 1 且元素为空串的数组，Integer.parseInt("") 抛 NumberFormatException。

序列化后忘记 trim 或用了多余分隔符："5 3 2 4 8 7 9 " 末尾多一个空格，Java 的 split(" ") 虽然会丢弃尾部空串，但换成 split(" ", -1) 或其他语言就会多出一个空 token，解析时抛异常。

判断写成闭区间 value < lower || value > upper：还原 "5 3 5" 这种含重复值的输入时（虽然本题保证不重复，但同样的代码迁移到允许重复的变体上）第二个 5 会被当成 5 的右孩子，破坏严格有序性。

反序列化末尾不判 index == values.length：还原 "5" 时，构造 5 的左孩子会去读下标 1，直接数组越界。

相似题目

题目	难度	考察点
297. 二叉树的序列化与反序列化	困难	任意二叉树没有有序性可用，必须给每个空孩子写占位符，是本题的通用退化版
428. 序列化和反序列化 N 叉树	困难	孩子数不固定，要额外编码每个节点的子节点个数或用配对的结束标记
1008. 前序遍历构造二叉搜索树	中等	直接给出前序数组，就是本题反序列化的那一半，可用来单独练上下界写法
105. 从前序与中序遍历序列构造二叉树	中等	没有 BST 性质，只能靠中序数组定位根的位置来切分左右子树
106. 从中序与后序遍历序列构造二叉树	中等	根在后序末尾，递归要从右子树先建，顺序与 105 相反
108. 将有序数组转换为二叉搜索树	简单	只给中序（升序）数组，结构不唯一，取中点自选一棵平衡树即可
331. 验证二叉树的前序序列化	中等	只判断带占位符的前序串是否合法，用槽位计数即可，无需真正建树
536. 从字符串生成二叉树	中等	用括号嵌套编码结构，还原时要做括号匹配的解析
606. 根据二叉树创建字符串	中等	只做序列化方向，难点在于何时可以省略空括号对
652. 寻找重复的子树	中等	把子树序列化结果当哈希键做去重，是序列化技巧的一种应用而非还原
LCR 048. 二叉树的序列化与反序列化	困难	与 297 同题，可直接套用带占位符的通用写法
剑指 Offer 37. 序列化二叉树	困难	与 297 同题，官方题解多用层序 BFS 编码，可对照前序 DFS 的差异