CS-Notes 剑指 Offer 题解：二叉树的序列化与反序列化（前序遍历 + 空节点占位）全解

二叉树无法像数组一样直接落盘或跨进程传输，面试中的高频考点"序列化二叉树"要求你把它编码成字符串、并能从字符串无损还原。本文基于 CS-Notes 仓库 [notes/37. 序列化二叉树.md](https://gitcode.com/GitHub_Trending/cs/CS-Notes/blob/b70121d377cb6005eb65f12b098cd5decd905669/notes/37. 序列化二叉树.md?utm_source=gitcode_repo_files) 的完整题解展开：先继承原文档的题目要求与标准解法代码，再逐步拆解"为什么必须保留空节点信息"、原文解法中可变字符串字段的消费逻辑、时间复杂度细节与边界情况，并给出基于索引指针的等价改写，帮助你掌握一棵任意二叉树在字符串表示上的无损编码原理。

题目要求：Serialize 与 Deserialize 必须互为逆操作

原题出自《剑指 Offer》第 37 题，在仓库中收录于 剑指 Offer 题解 - 目录 的"树"分类下。题目要求：

请实现两个函数，分别用来序列化和反序列化二叉树。

这实际上是一个"编码/解码必须可逆"的双向约束问题：

• 序列化：把内存中的 TreeNode 树转换为字符串。编码方案必须携带足够的结构信息，使得任何形状（左斜、右斜、完全二叉树、单节点、空树）都能被唯一还原；
• 反序列化：按同一套编码规则解析字符串，重建出与原来完全一致（节点值、父子关系、左右位置）的树。

一个常见的误区是只用"非空节点的前序遍历"作为编码结果。可以推断：前序序列 1 2 3 既可以解释为"1 的左孩子是 2、2 的左孩子是 3"，也可以解释为"1 的右孩子是 2、2 的右孩子是 3"等多种结构——不记录"哪里没有孩子"，就无法区分树形。因此必须在遍历结果中显式标记空子树，这是本解法的核心思想。

标准解法：前序遍历 + # 占位符（原文档代码）

原文档给出的 Java 解法如下，它使用 # 表示空节点、用单个空格分隔 token，按前序顺序（根 → 左子树 → 右子树）输出：

private String deserializeStr;

public String Serialize(TreeNode root) {
    if (root == null)
        return "#";
    return root.val + " " + Serialize(root.left) + " " + Serialize(root.right);
}

public TreeNode Deserialize(String str) {
    deserializeStr = str;
    return Deserialize();
}

private TreeNode Deserialize() {
    if (deserializeStr.length() == 0)
        return null;
    int index = deserializeStr.indexOf(" ");
    String node = index == -1 ? deserializeStr : deserializeStr.substring(0, index);
    deserializeStr = index == -1 ? "" : deserializeStr.substring(index + 1);
    if (node.equals("#"))
        return null;
    int val = Integer.valueOf(node);
    TreeNode t = new TreeNode(val);
    t.left = Deserialize();
    t.right = Deserialize();
    return t;
}

两个公开函数 Serialize / Deserialize 是牛客等刷题平台约定的函数签名；内部递归函数与实例字段 deserializeStr 承担状态传递的职责。下面逐段说明。

Serialize：递归的前序编码

• 空树返回 "#"：这是整个编码的"终止符"，占位符与真实节点值天然可区分；
• 非空节点按 root.val + " " + 左子树编码 + " " + 右子树编码 拼接，即标准的**前序（根左右）**递归顺序；
• 由于每个节点（含空）恰好贡献一个 token，n 个真实节点的树会输出 2n - 1 个 token（n 个值 + n-1 个 #）。

Deserialize：按前序约定"边消费、边建树"

私有递归函数 Deserialize() 每次执行只消费一个 token，其逻辑分四步：

1. 判空：deserializeStr.length() == 0 时返回 null，对应字符串恰好用尽；
2. 取 token：用 indexOf(" ") 找到第一个空格，截取出第一个 token，并同步把 deserializeStr 裁剪为该 token 之后的剩余部分——这是"游标前移"的字符串版实现；
3. 区分占位符：token 为 # 则返回 null（代表该子树为空）；
4. 递归建树：否则解析 Integer.valueOf(node) 创建节点，并严格按前序顺序先递归构建 t.left、再递归构建 t.right。

序列化端"根 → 左 → 右"地吐 token，反序列化端"根 → 左 → 右"地吃 token，两侧的遍历顺序一一对应，这就是可逆性的来源。

手工推演：一棵含右斜结构的树如何编码与还原

以如下二叉树为例：

      1
     / \
    2   3
         \
          4

按 Serialize 规则逐层展开：

节点	编码结果
节点 4	4 # #
节点 3（左空、右为 4）	3 # 4 # #
节点 2（左右皆空）	2 # #
节点 1（根）	1 2 # # 3 # 4 # #

即最终字符串为 "1 2 # # 3 # 4 # #"，共 9 个 token（5 个真实节点 + 4 个 #，满足 2n-1）。

Deserialize 消费该字符串的过程：读 1 建根 → 递归左子树读 2 建节点 → 读 #、# 判定 2 的左右皆空 → 回到根递归右子树读 3 → 读 # 判定 3 左空 → 读 4 建节点 → 读 #、# 判定 4 的左右皆空 → token 恰好用尽。还原出的树与原始树逐节点一致。注意第 4、5 个 token 正是区分"2 的右空"与"3 的左空"的关键——若没有这两个 #，就无法知道第 5 个值 3 应该挂在谁下面。

解法实现细节与复杂度

字符串游标的可变字段设计。 原文档没有把"读取位置"作为参数在递归间传递，而是把剩余字符串放在实例字段 deserializeStr 上，每次递归裁剪掉已消费的头部。这与"传一个 int index 参数"的写法等价，后者避免了重复创建子串：

// 基于索引指针的等价改写（仅展示 Deserialize 侧）
private int idx;
private String[] tokens;

public TreeNode Deserialize(String str) {
    tokens = str.split(" ");
    idx = 0;
    return build();
}

private TreeNode build() {
    if (idx >= tokens.length)
        return null;
    String node = tokens[idx++];
    if (node.equals("#"))
        return null;
    TreeNode t = new TreeNode(Integer.valueOf(node));
    t.left = build();
    t.right = build();
    return t;
}

时间复杂度。 Serialize 中每个节点恰好处理一次，时间 O(n)。Deserialize 的 token 数也是 2n-1，逻辑上仍是 O(n)；但需注意原文档实现中每次 substring 都会复制剩余字符串的字符数组（Java 7u6 之后 substring 共享实现被移除），从源码结构看，对极端斜树这类递归深度 O(n) 的输入，字符串拷贝开销最坏可累计到 O(n²)。若对长链树性能敏感，可改用上面的索引/分词写法。

空间复杂度。 两个方向都依赖递归栈，空间 O(h)，h 为树高；斜树下退化为 O(n)。

边界情况。 结合代码可以直接验证：

• 空树：Serialize(null) 得到 "#"，Deserialize("#") 读一个 # 返回 null，互逆成立；
• 单节点树：val # #，同样可逆；
• 节点值可重复：本方案与"前序 + 中序重建树"（见 7. 重建二叉树，该题明确要求值不重复）不同，占位符标记的是结构而非靠数值定位，因此重复值不影响正确性；
• 分隔符取单个空格，token 内部不含空格，故负数值（如 -5）也不会破坏 Integer.valueOf 的解析。

与 Java 内置序列化的关系：同名概念，不同层次

CS-Notes 在 Java IO 一节中系统讲解了 Java 的对象序列化机制：实现 Serializable 标记接口的类通过 ObjectOutputStream.writeObject() 写入字节流、ObjectInputStream.readObject() 读回，且 transient 字段会被跳过。两者虽然都叫"序列化"，但层次不同：

• Java 内置序列化是 JVM 层面的对象字节流，编码格式不透明、跨语言不可读，且对依赖类版本敏感；
• 本文的前序 + 占位符方案是面向树结构本身的可读文本编码，人类可直接检查内容，也便于存入普通文本协议、日志或数据库字段；
• 若 TreeNode 中确实包含需要持久化的额外字段，也可以让节点类实现 Serializable 走内置机制，但此时"父子指针构成环"的图问题需要另行处理（如重写 writeObject），这也是面试中常被追问的延伸点。

相关题目与知识关联

本题考察的"前序遍历 + 递归重建"套路，在仓库的剑指 Offer 题解树分类中有一组可直接对照的题：

• 7. 重建二叉树：由前序 + 中序确定树（要求值不重复），可理解为"输入两遍遍历，本题则是一遍带空标记的遍历"；
• 32.1 从上往下打印二叉树：层次遍历同样能把树转成序列，但需额外记录每层节点数才能还原，前序方案更直接；
• 55.1 二叉树的深度、34. 二叉树中和为某一值的路径：同属递归处理树结构的典型题，可用于巩固"递归进出栈"思维；
• Java IO：Serializable / transient / 自定义 writeObject，理解 Java 侧序列化体系。

小结

• 二叉树无损序列化的关键，是在遍历结果中显式记录空子树（# 占位符），使前序序列成为树的唯一编码；
• Serialize 与 Deserialize 必须使用同一遍历顺序（前序：根 → 左 → 右），反序列化时先吃左子树 token 再吃右子树 token，与编码严格对称；
• 原文档实现用可变字段 deserializeStr 承担游标角色，简洁直观；索引指针写法可避免重复子串拷贝，对斜树更友好；
• 与 Java 内置对象序列化相比，文本级树编码可读、可移植，是面试与工程（日志、接口协议）中更常用的树持久化手段。