LeetCode LCR 048. 二叉树的序列化与反序列化
目录
题目描述
题意分析
题目目标：设计一对互逆的操作，把任意一棵二叉树编码成字符串，再把该字符串解码回一棵结构与值都完全相同的树。判题只检查"解码结果与原树同构且对应节点值相等"，并不规定编码格式。
核心约束：编码格式可以自选，这是本题最大的自由度，也是唯一的设计点——只要自己的编码和解码能对上就行。真正的硬约束是信息不能丢：仅靠一种遍历序列（前序或中序或层序的非空节点）无法唯一还原一棵二叉树，必须把"某个位置是空"这一事实也写进字符串。
边界处理：空树要能编码也要能解码回空；单节点树；只有左孩子或只有右孩子的偏斜结构（这正是空位信息不可省略的原因）；节点值可以是负数，也可以是多位数，所以必须有分隔符。
实现取舍：编码与解码必须使用同一套遍历顺序，且解码时消费记号的顺序要与编码时产出的顺序严格对齐；分隔符和空标记要选不会与节点值混淆的字符。
解法：深度优先搜索
核心思路
先排除一个诱人的错误方向：只把非空节点按某种顺序写出来。树
[1, 2]和树[1, null, 2]的非空层序序列都是1, 2，解码时无从分辨 2 该挂左边还是右边，说明这种编码是有损的。要无损，就必须让"空"也占一个位置——空位恰恰携带了结构信息。
确定了这一点之后，选哪种遍历顺序反而是次要的。这里选择逐层推进：从根开始，每弹出一个非空节点就写下它的值并把它的左右孩子（哪怕是空）一并入队，弹出空节点则写下一个#且不再扩展。这样产出的记号序列有一条很强的性质——非空节点的孩子记号，一定按照该节点被写出的先后顺序成对地排在序列后方。
解码正是靠这条性质：维护一个装着"已经建好但孩子还没认领"的节点的容器，同时用指针i从左到右扫描记号。每次弹出一个待认领的节点，就从序列里连取两个记号分别作为它的左孩子和右孩子，遇到#就保持空指针，遇到数值就新建节点并放回容器等待认领自己的孩子。
不变量有两条：其一，容器中节点的排列顺序与编码时它们被写出的顺序完全一致；其二，指针i始终指向"下一个尚未被认领的孩子记号"。两条不变量共同保证了每个节点认领到的正是编码时属于它的那两个位置，编码与解码于是严格互逆。
解题步骤
- 序列化先处理空树，直接返回空串。为什么用空串而不是
"#"：解码端只要以"空串即空树"作为约定，两端就能对上；关键在于这个约定必须双向一致，而不在于选了哪种表示。- 根入队后循环弹出节点：非空则追加
节点值 + ","并把左右孩子无条件入队（即便是空），为空则只追加"#,"。为什么空孩子也要入队：正是这些空占位在输出里写下#，把"这里没有孩子"变成显式信息；不入队就退化成有损编码。- 为什么空节点不再扩展：空节点没有孩子，若继续入队两个空会让序列无限膨胀，且解码端也不会去为它认领孩子。
- 用逗号分隔每个记号。为什么必须有分隔符：节点值可能是多位数或负数，
12与1, 2若不分隔就完全无法区分。- 反序列化先判空串返回空，再按逗号切分得到记号数组，用首个记号建根并入队，指针
i从 1 开始。为什么根要单独建：根没有父亲来认领它，只能由解码流程直接消费第 0 个记号。- 循环条件是"容器非空且
i未越界"，每轮弹出一个待认领节点，读vals[i]决定左孩子后i++，再读vals[i]决定右孩子后i++。为什么读右孩子前要再判一次i < vals.length：末尾的空记号可能被切分丢弃或提前耗尽，多这一次判断能防止越界。- 为什么只有非
#的记号才入队：#代表空位，不产生节点，自然也不需要认领孩子；只有新建出来的真实节点才会在后续轮次里认领属于自己的两个记号。- 以
具体用例：树[1, 2, 3, null, null, 4, 5]（根 1；左孩子 2 是叶子；右孩子 3 的左右孩子分别是 4、5）走一遍。序列化时依次弹出 1（写1，入队 2、3）、2（写2，入队两个空）、3（写3，入队 4、5）、空（写#）、空（写#）、4（写4，入队两个空）、5（写5，入队两个空），之后连续弹出八个空各写一个#，得到1,2,3,#,#,4,5,#,#,#,#,#,#,。反序列化时切分出记号数组，建根 1 并入队，i = 1。第一轮弹出 1，读到2建左孩子并入队，i = 2读到3建右孩子并入队，i = 3。第二轮弹出 2，读到#左孩子留空，i = 4又读到#右孩子留空，i = 5。第三轮弹出 3，读到4、5分别建成左右孩子并入队，i = 7。第四轮弹出 4，连读两个#；第五轮弹出 5，同样连读两个#，容器清空，返回的树与原树完全一致。
代码实现
// 核心实现：深度优先搜索，维护必要状态并避免重复处理。
class Codec {
public String serialize(TreeNode root) {
if (root == null) {
return "";
}
StringBuilder sb = new StringBuilder();
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
if (node == null) {
sb.append("#,");
} else {
sb.append(node.val).append(",");
queue.offer(node.left);
queue.offer(node.right);
}
}
return sb.toString();
}
public TreeNode deserialize(String data) {
if (data.isEmpty()) {
return null;
}
String[] vals = data.split(",");
TreeNode root = new TreeNode(Integer.parseInt(vals[0]));
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
int i = 1;
while (!queue.isEmpty() && i < vals.length) {
TreeNode node = queue.poll();
if (!vals[i].equals("#")) {
node.left = new TreeNode(Integer.parseInt(vals[i]));
queue.offer(node.left);
}
i++;
if (i < vals.length && !vals[i].equals("#")) {
node.right = new TreeNode(Integer.parseInt(vals[i]));
queue.offer(node.right);
}
i++;
}
return root;
}
}
// 核心实现：深度优先搜索，维护必要状态并避免重复处理。
type Codec struct{}
func Constructor() Codec { return Codec{} }
func (c *Codec) serialize(root *TreeNode) string {
if root == nil {
return ""
}
var res []string
queue := []*TreeNode{root}
for len(queue) > 0 {
node := queue[0]
queue = queue[1:]
if node == nil {
res = append(res, "#")
} else {
res = append(res, strconv.Itoa(node.Val))
queue = append(queue, node.Left, node.Right)
}
}
return strings.Join(res, ",")
}
func (c *Codec) deserialize(data string) *TreeNode {
if data == "" {
return nil
}
vals := strings.Split(data, ",")
root := &TreeNode{Val: mustAtoi(vals[0])}
queue := []*TreeNode{root}
i := 1
for len(queue) > 0 && i < len(vals) {
node := queue[0]
queue = queue[1:]
if vals[i] != "#" {
node.Left = &TreeNode{Val: mustAtoi(vals[i])}
queue = append(queue, node.Left)
}
i++
if i < len(vals) && vals[i] != "#" {
node.Right = &TreeNode{Val: mustAtoi(vals[i])}
queue = append(queue, node.Right)
}
i++
}
return root
}
func mustAtoi(s string) int {
n, _ := strconv.Atoi(s)
return n
}
复杂度分析
- 时间复杂度：编码与解码均为 $O(n)$。凭什么：编码时每个真实节点入队出队一次、每个空位入队出队一次，而空位数量恰好是
n + 1，都是线性的；解码时每个记号只被指针i扫过一次，每个节点只被认领一次。- 空间复杂度：$O(n)$。凭什么：输出字符串长度与记号数同阶，容器在任意时刻至多容纳相邻两层的节点与空位，最坏也是 $O(n)$。
关键点总结
- 单一遍历序列不足以还原二叉树，必须补上空位标记或者再给一条不同顺序的序列，这是这类题的第一性原理；答题时用
[1, 2]与[1, null, 2]这组反例开场最有说服力。- 编码与解码是一对契约：遍历顺序、空标记、分隔符三件事必须两端完全一致，任何一端单独"优化"都会立刻破坏互逆性。
- 逐层编码的解码之所以能用"待认领节点容器 + 单向扫描指针"完成，靠的是"孩子记号按父亲被写出的顺序成对出现"这条性质，把它讲出来比背代码重要。
- 空位也要占位入队但不再扩展，这条规则同时保证了信息完整与序列有限，是编码端最容易写错的一行。
- 面试视角：面试官更常见的期待是前序递归版本——序列化时空节点写
#，反序列化时用一个全局指针按前序消费，遇到#返回空，否则建节点并递归建左右子树。层序与前序两种写法都要能白板写出，并说清"前序递归代码更短、空间 $O(h)$，层序更贴近题目给的示例格式"，同时主动提到分隔符与负数值的处理，才是完整回答。
易错点总结
- 错误写法：只序列化非空节点，不写空标记 → 树
[1, 2]与[1, null, 2]编码后都是1,2，解码只能还原出其中一种，另一种结构永久丢失。- 错误写法：序列化时不入队空孩子，只在遇到空孩子时写
#但不占位 → 记号与位置的对应关系错位，解码时孩子被认领给错误的父亲，树形整体乱掉。- 错误写法：空节点入队后仍然把它的两个"孩子"继续入队 → 队列永远不为空，序列无限增长，程序直接超时或内存溢出。
- 错误写法：不加分隔符直接拼接数字 → 树
[12, 3]编码成123#...，解码时无法判断首个记号是1还是12，还原出的值完全错误。- 错误写法：用
-或数字字符作空标记 → 节点值可能为负数，-1与空标记混淆，解码时把真实节点当成空位丢弃。- 错误写法：解码时读完左孩子记号后忘记
i++，或读右孩子前不判i < vals.length→ 前者让左右孩子读到同一个记号导致左右子树相同，后者在记号耗尽时抛出数组越界异常。- 错误写法：解码时把
#也建成节点并入队 → 空位变成值为 0 的真实节点，树[1, null, 2]解码出多余的左孩子，节点数对不上。- 错误写法：空树序列化返回
""但解码端用data == null判断 → 空串没被拦住，split得到长度为 1 的数组再parseInt("")抛出数字格式异常。- 错误写法：解码循环条件只写
i < vals.length而不检查容器非空 → 序列末尾若有多余记号，弹出空容器时抛异常。- 错误写法：序列化用层序而解码按前序消费（或反过来） → 树
[1, 2, 3]解码成一条链，结构与原树完全不符，本质是两端契约不一致。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 449. 序列化和反序列化二叉搜索树 | 中等 | 有序性让空标记可省，编码可以压得更短 |
| 428. 序列化和反序列化 N 叉树 | 困难 | 孩子个数不固定，必须额外编码子节点数量或结束符 |
| 105. 从前序与中序遍历序列构造二叉树 | 中等 | 用两条无空位序列还原结构，靠中序定位划分点 |
| 331. 验证二叉树的前序序列化 | 中等 | 只判断编码串合法性，可用槽位计数而不真正建树 |
| 606. 根据二叉树创建字符串 | 中等 | 用括号表达结构，重点在何时可以省略多余的空括号 |
| 652. 寻找重复的子树 | 中等 | 把序列化当作子树指纹用于去重，考察编码的唯一性 |