LeetCode 剑指 Offer 37. 序列化二叉树

2024-10-25 HGNULB 约 11 分钟

文章信息 4 个分类 6 个标签

分类

题目描述

✅ 剑指 Offer 37. 序列化二叉树

题意分析

题目目标：设计一对互逆的方法：serialize 把一棵二叉树编码成字符串，deserialize 把该字符串还原成结构完全相同的树。判题只要求「还原出来的树和原树同构且节点值一致」，不规定编码格式。

核心约束：编码格式自由，但必须自洽——序列化时怎么写空位，反序列化时就得怎么读空位。这条约束是全题的核心：只记录非空节点的值是不够的，因为「前序遍历 [1,2]」既可能是 2 挂在 1 的左边，也可能挂在右边，信息量不足以唯一确定形状。所以空指针必须显式落到字符串里，这是编码可逆的充分条件。

边界处理：空树要能来回转换而不炸；单节点树；节点值可能是负数，所以分隔符不能用 -；值可能是多位数，所以不能按字符定长切分；只有左子树或只有右子树的「瘸腿」节点必须靠占位符区分。

实现取舍：编码顺序可以是前序 DFS，也可以是层序 BFS。前者递归写起来最短，后者产生的字符串与 LeetCode 题面展示的数组格式一致、调试时肉眼可读，且不吃递归栈。两者难度相当，本文用层序。

解法：深度优先搜索

核心思路

先说清楚为什么不能只写非空节点。假设只把前序遍历 1,2 写进字符串，反序列化时无从判断 2 是 1 的左孩子还是右孩子；再假设同时给出前序和中序两个序列（经典的「由两个遍历重建二叉树」），确实可以唯一还原，但那要求节点值互不重复，而本题没有这个保证。所以正确的方向只有一个：把空指针也当成节点写进去。补上空位之后，任何一种遍历序列都能唯一还原树，因为每读到一个值就能立刻确定它挂在哪个父节点的哪一侧。

具体选层序遍历。序列化时用一个队列做标准 BFS，但不跳过空节点：出队的若是真实节点，就写下它的值并把它的左右孩子（哪怕是 null）一起入队；出队的若是 null，就写一个 # 占位，且不再往下扩展。这样得到的字符串就是「完全展开的层序序列」。

反序列化是这个过程的严格镜像。关键不变量是：队列里存放的是「已经建好但孩子还没填」的节点，而下标 i 指向「下一个待消费的孩子槽位」。因为序列化时每个非空节点恰好写出两个孩子槽位、每个空节点不写任何槽位，所以出队一个节点就正好消费两个 token，两边的节奏永远对齐，i 不会错位也不会越界。

分隔符选逗号、空位符选 #，都是为了避开数值本身的字符集：值可能是负数（含 -）和多位数（含多位数字），但绝不会包含逗号或井号，因此按逗号切分之后每个 token 要么是合法整数、要么是 #，解析无歧义。

空树单独约定：Java 版序列化返回 null、反序列化见到 null 直接返回 null；Go 版对应地用空字符串。这不是偷懒——如果不特判，空树会被编码成单独一个 #，反序列化时读 vals[0] 再 Integer.valueOf("#") 会抛异常，与其在主流程里加分支，不如在入口处一次性挡掉。

解题步骤

序列化第一步：root == null 直接返回 null（Go 返回空串）。 为什么单独挡掉：主循环假设至少存在一个真实节点可以作为根，空树不满足这个前提。

序列化第二步：根入队，循环出队。 出队节点非空时，把它的值追加到结果列表，并把 node.left、node.right 无条件入队（可能是 null）；出队节点为空时，只追加 #。为什么空孩子也要入队：它们在字符串中占位，是后续还原形状的唯一依据；为什么 # 不再扩展：空节点没有孩子，写两个 # 只会让字符串无限膨胀且破坏「非空节点恰好对应两个槽位」的节奏。

序列化第三步：用逗号把列表拼成字符串。 为什么用 String.join 而不是循环 +=：字符串拼接是 $O(n^2)$，节点数上万时会明显变慢，这在设计题里是会被追问的点。

反序列化第一步：入参为 null/空串时返回 null。 与序列化的空树约定对齐。

反序列化第二步：按逗号切分得到 vals，用 vals[0] 建根节点并入队，i 置为 1。 为什么 i 从 1 开始：0 号 token 已经被根消费掉了，i 此后始终指向「下一个待填的孩子槽位」。

反序列化第三步：循环出队一个节点，连续消费两个 token。 第一个 token 不是 # 就建左孩子并入队，之后 i++；第二个 token 不是 # 就建右孩子并入队，之后 i++。为什么无论是不是 # 都要 i++：# 同样占据一个槽位，跳过它才能保持下标与序列化时的写入节奏一致；漏掉这次自增会让后面所有 token 整体错位。为什么只有非空孩子才入队：只有它们将来还需要填孩子，空节点没有槽位可消费。

反序列化第四步：队列空时返回根。 此时 i 恰好走到 vals.length，可以作为一条自检。

以 root = [1, 2, 3, null, null, 4, 5] 走一遍序列化：队列初始 [1]。出队 1，写下 1，把 2 和 3 入队 → 队列 [2, 3]。出队 2，写下 2，它的两个孩子都是空，入队两个 null → 队列 [3, null, null]。出队 3，写下 3，把 4 和 5 入队 → 队列 [null, null, 4, 5]。出队 null，写 #；再出队 null，写 # → 队列 [4, 5]。出队 4，写下 4，入队两个 null；出队 5，写下 5，入队两个 null → 队列 [null, null, null, null]。连续出队四个空，写四个 #，队列清空。最终字符串是 1,2,3,#,#,4,5,#,#,#,#，共 11 个 token。

再走一遍反序列化：切分得到 11 个 token。建根 1，i = 1，队列 [1]。

出队 1：vals[1] = "2" 非 #，建左孩子 2 并入队，i = 2；vals[2] = "3" 非 #，建右孩子 3 并入队，i = 3。队列 [2, 3]。

出队 2：vals[3] = "#"，不建左孩子，i = 4；vals[4] = "#"，不建右孩子，i = 5。注意这两次 i++ 照常执行——这正是「空位也占槽位」的体现。队列 [3]。

出队 3：vals[5] = "4"，建左孩子 4 入队，i = 6；vals[6] = "5"，建右孩子 5 入队，i = 7。队列 [4, 5]。

出队 4：vals[7]、vals[8] 都是 #，不建孩子，i = 9。出队 5：vals[9]、vals[10] 都是 #，i = 11。队列清空，i 恰好等于 vals.length = 11，自检通过。返回的树与原树完全一致。

代码实现

class Codec {

    public String serialize(TreeNode root) {
        if (root == null) {
            return null;
        }
        List<String> answer = new ArrayList<>();
        Deque<TreeNode> q = new LinkedList<>();
        q.offer(root);
        while (!q.isEmpty()) {
            TreeNode node = q.poll();
            if (node != null) {
                answer.add(node.val + "");
                q.offer(node.left);
                q.offer(node.right);
            } else {
                answer.add("#");
            }
        }
        return String.join(",", answer);
    }

    public TreeNode deserialize(String data) {
        if (data == null) {
            return null;
        }
        String[] vals = data.split(",");
        int i = 0;
        TreeNode root = new TreeNode(Integer.valueOf(vals[i++]));
        Deque<TreeNode> q = new ArrayDeque<>();
        q.offer(root);
        while (!q.isEmpty()) {
            TreeNode node = q.poll();
            if (!"#".equals(vals[i])) {
                node.left = new TreeNode(Integer.valueOf(vals[i]));
                q.offer(node.left);
            }
            ++i;
            if (!"#".equals(vals[i])) {
                node.right = new TreeNode(Integer.valueOf(vals[i]));
                q.offer(node.right);
            }
            ++i;
        }
        return root;
    }
}

type Codec struct {
}

func Constructor() Codec {
    return Codec{}
}

func (this *Codec) serialize(root *TreeNode) string {
    if root == nil {
        return ""
    }
    q := []*TreeNode{root}
    answer := []string{}
    for len(q) > 0 {
        node := q[0]
        q = q[1:]
        if node != nil {
            answer = append(answer, strconv.Itoa(node.Val))
            q = append(q, node.Left)
            q = append(q, node.Right)
        } else {
            answer = append(answer, "#")
        }
    }
    return strings.Join(answer, ",")
}

func (this *Codec) deserialize(data string) *TreeNode {
    if data == "" {
        return nil
    }
    vals := strings.Split(data, ",")
    v, _ := strconv.Atoi(vals[0])
    i := 1
    root := &TreeNode{Val: v}
    q := []*TreeNode{root}
    for len(q) > 0 {
        node := q[0]
        q = q[1:]
        if x, err := strconv.Atoi(vals[i]); err == nil {
            node.Left = &TreeNode{Val: x}
            q = append(q, node.Left)
        }
        i++
        if x, err := strconv.Atoi(vals[i]); err == nil {
            node.Right = &TreeNode{Val: x}
            q = append(q, node.Right)
        }
        i++
    }
    return root
}

复杂度分析

时间复杂度：序列化与反序列化均为 $O(n)$。凭什么：设树有 $n$ 个真实节点，则空槽位恰好 $n + 1$ 个，字符串总 token 数是 $2n + 1$，两个方向都对每个 token 做常数次操作（入队、出队、追加或解析各一次）；String.join 和 split 也都是线性的。

空间复杂度：$O(n)$。凭什么：队列在最宽的一层可能同时容纳 $O(n)$ 个节点（完全二叉树的最后一层约占一半节点），输出的字符串同样是 $O(n)$ 量级；由于用的是迭代式 BFS，不额外消耗递归栈。

关键点总结

可逆编码的充要条件是「形状信息不能丢」，最简单的做法就是把空指针也写进去。 只写非空值的方案在值可能重复时一定不可逆，这是本题第一道坎。

序列化和反序列化必须共享同一套节奏约定。 本题的约定是「每个非空节点恰好对应两个孩子槽位，每个空节点不产生槽位」，两边都严格遵守，下标才不会错位。

分隔符和占位符要挑输入值不可能包含的字符。 值有负号和多位数，所以逗号 + # 是安全组合，用 - 或定长切分都会翻车。

空树在入口处一次性特判，好过在主循环里到处加分支。 设计题里这种「把边界收敛到边界上」的习惯很值钱。

拼接字符串用 join/strings.Builder 而不是 +=。 这是设计题里区分「能跑」和「能上线」的细节，面试官经常顺口一问。

面试视角：先明确问清「格式是否有要求」「值是否可能重复」，再给出「空位显式编码」的核心判断，然后二选一实现（说明前序 DFS 更短、层序 BFS 更易读且无递归栈风险）。写完后主动补：反序列化的下标推进是最容易错的地方，可以用「结束时 i 恰好等于 token 总数」做自检；如果树极深，DFS 版本要考虑改成显式栈以防爆栈。

易错点总结

错误写法：序列化时跳过空孩子，只写非空节点 → 用例 [1,2]（2 是左孩子）与 [1,null,2]（2 是右孩子）会编码出同样的 1,2，反序列化后两棵树必然有一棵是错的。

错误写法：序列化时给空节点也入队两个 null 孩子 → 用例 [1]，根写下 1 后入队两个空，两个空又各自入队两个空，队列永远不空，程序死循环或内存溢出。

错误写法：反序列化时遇到 # 就不执行 i++ → 用例 1,2,3,#,#,4,5,#,#,#,#，处理节点 2 时两个 # 都不推进下标，接下来给节点 3 分配的孩子会错误地取到 vals[3] = "#" 和 vals[4] = "#"，节点 4、5 全部丢失，还原出的树是 [1,2,3]。

错误写法：反序列化时把 # 也建成节点入队 → 用例 1,2,3,#,#,4,5,#,#,#,#，Integer.valueOf("#") 直接抛 NumberFormatException；即便用 try-catch 兜住，空节点入队后还要消费两个不存在的槽位，vals[i] 越界。

错误写法：用空格或短横线做分隔符 → 用例含负值的树 [-1,-2,-3]，用 - 切分会把 -1 拆成空串和 1，解析失败。

错误写法：用固定长度切分字符串（如每 2 个字符一个节点） → 用例 [100, 5]，100 占 3 位、5 占 1 位，定长切分立刻错位。

错误写法：用 0 或 -1 表示空节点而不是 # → 用例 [1,0,-1]，真实的 0 和 -1 会被误判为空指针，还原出的树丢失这两个节点。

错误写法：空树序列化成 "#" 但反序列化不特判 → 用例空树，vals = ["#"]，Integer.valueOf("#") 抛异常。

错误写法：序列化返回 null 而反序列化只判 data.isEmpty() → 用例空树，null.isEmpty() 抛空指针；两侧的空约定必须严格配对。

错误写法：序列化用 answer += node.val + "," 逐次拼接 → 用例节点数 $10^4$ 的树，字符串拼接是 $O(n^2)$ 的字符复制，容易超时；应改用 List + join 或 StringBuilder。

错误写法：反序列化的循环条件写成 i < vals.length 而不是「队列非空」 → 用例 1,2,3,#,#,4,5,#,#,#,#，队列先于下标耗尽时会继续出队空队列，抛 NoSuchElementException。

相似题目

题目	难度	考察点
297. 二叉树的序列化与反序列化	困难	主站同题，可用来对照前序 DFS 写法与本文层序写法的字符串差异
449. 序列化和反序列化二叉搜索树	中等	BST 的有序性使得空位可以完全省略，考点变成如何用值域上下界还原结构
LCR 048. 二叉树的序列化与反序列化	困难	专题版同题，适合再练一遍「递归反序列化时如何共享游标下标」