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

约 6 分钟
文章信息 4 个分类 6 个标签
分类
LeetCode 困难 剑指 Offer 剑指 Offer（第 2 版）
标签
字符串 深度优先搜索 树 广度优先搜索 二叉树 设计

题目描述

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

image-20261001230752562

image-20260928194957110

image-20260928194957111

image-20260928194957112

题意分析

将二叉树编码成字符串，再从该字符串恢复节点值和左右孩子关系都相同的树。值可以重复，因此不能仅靠数值判断结构；编码格式可自行约定，但序列化和反序列化必须配套。

解法：带空位标记的层序编码

核心思路

[!blue]

使用层序遍历，按从上到下、同层从左到右的顺序输出。真实节点写入数值，并把左右孩子都入队；空节点写入 #，但不再为它扩展孩子。这样左右空位也被保留，节点值相同或某侧缺失都不会造成歧义。

用逗号分隔每个值和空标记，使多位数、负数仍能作为一个完整 token 读取。空树单独约定：当前 Java 实现返回 null，Go 实现返回空串，各自的反序列化函数先识别同一约定。

还原非空树时，先读取根值，并将根放入待填孩子的队列。每取出一个真实父节点，就依次消费左、右两个 token：遇到数值则创建对应孩子并入队，遇到 # 则保持该孩子为空。无论是否为空，两个槽位都必须各消费一次。

两边真实父节点的处理顺序相同，每个父节点的左右位置又都有明确标记，因此可以逐层唯一恢复原树。序列化队列允许空节点，反序列化队列只放真实节点；两者职责不同，不能照搬空节点入队规则。后者队列为空时，所有真实节点的孩子槽位都已处理完。

解题步骤

  1. 空树按各语言约定编码：Java 为 null，Go 为空串。
  2. 序列化时 BFS，空孩子也入队并输出 #，空节点不继续扩展。
  3. 以逗号分隔 token；反序列化先建根，再逐个填充队首节点的两个孩子。
  4. 每个孩子槽位都推进下标，只有非空孩子才入队。

代码实现

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

import (
    "strconv"
    "strings"
)

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 个真实节点和 n + 1 个空孩子标记，共 2n + 1 个 token。
  • 空间复杂度：$O(n)$，保存编码结果、拆分后的 token 和层序队列。

关键点总结

[!green]

反序列化输入按题意来自同一序列化器；左右槽位的消费顺序必须与编码顺序一致。

易错点总结

[!yellow]

  • Java 序列化队列含 null，使用支持空元素的 LinkedList，不能直接换成 ArrayDeque。
  • 只写非空值会丢失左右孩子位置，无法唯一还原结构。
  • 遇到 # 也必须移动 token 下标，且不能把 # 继续扩展成孩子。
  • 空树约定必须配对；值分隔符不能与负号混淆。

相似题目

题目 难度 关联与区别
449. 序列化和反序列化二叉搜索树 中等 BST 的有序性质允许更紧凑的编码，普通二叉树不能依赖该性质省去结构信息。
331. 验证二叉树的前序序列化 中等 同样用空位标记描述结构，原题验证前序序列是否合法，本题按层序实际还原节点。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2024/91810127
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！