LeetCode LCR 048. 二叉树的序列化与反序列化
题目描述
题意分析
设计一对操作：把二叉树编码为字符串，再从字符串恢复出结构和值都相同的树。格式可以自行约定，但必须同时保留节点值和缺失孩子的位置；只记录非空节点值，无法判断一个孩子原来在左侧还是右侧。
解法：层序序列化与反序列化
核心思路
[!blue]
序列化按层序输出记号：非空节点写出完整整数值，并把左右孩子依次入队；空节点写
#，不再扩展孩子。记号之间用逗号分隔，因此负数和多位数也能作为一个完整字段解析。这种编码中，每个非空节点的两个孩子记号，都按父节点的层序出现顺序成对排列。空位也占一个记号，左右位置不会因孩子缺失而错位；空节点不继续扩展，又保证编码最终结束。
反序列化先读取根值，再用队列保存已经创建、尚待连接孩子的非空节点。每弹出一个父节点，就依次消费两个记号：第一个属于左孩子，第二个属于右孩子；数值记号创建节点并入队，
#保持空指针。解码队列始终与编码时非空父节点的处理顺序一致，扫描位置
i又始终指向下一个未消费的孩子记号。因此每个父节点都能取回自己的左右孩子，逐层恢复出的整棵树与原树完全相同。
解题步骤
- 空树编码为空串，解码空串时直接返回空。
- 非空树从根开始层序遍历，按“值或
#”输出记号；只有非空节点才把两个孩子加入队列。- 解码时按逗号拆分，使用首字段建立根，根入队，并让
i=1。- 按队列顺序取父节点，分别读取左右孩子字段；非空孩子建好后入队，等待连接它们自己的孩子。
- 队列处理完后返回根节点。
Java 编码保留末尾逗号，
String.split会丢弃末尾空字段；Go 用strings.Join连接记号，不附加末尾逗号。各自的编码与解码规则配套，解码输入按本实现生成的合法格式处理。即使只缺左孩子或只缺右孩子，#也会准确保留这一侧的空位。
代码实现
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;
}
}
import (
"strconv"
"strings"
)
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$ 个节点和 $n+1$ 个空孩子位置，总共输出 $2n+1$ 个记号；每个记号只生成、读取一次。
- 空间复杂度：$O(n)$，用于层序队列、编码字符串或拆分后的字段；反序列化还会创建 $n$ 个结果节点。
关键点总结
[!green]
- 空标记保存树的形状，分隔符保存整数的字段边界。
- 编码队列包含空节点；解码队列只保留需要连接孩子的非空节点。
- 每次解码一个父节点都依次消费左、右两个字段，消费顺序必须与编码一致。
易错点总结
[!yellow]
- 编码和解码必须约定同一种遍历顺序、分隔符及空节点标记。
- 需要保存缺失孩子的位置；只保存非空节点值不能区分左孩子和右孩子。
- 当前序列化队列包含 null，Java 使用允许 null 的 LinkedList，不能直接换成 ArrayDeque。
- 空树的编码与解码边界要一致，数字节点仍按完整字段解析。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 449. 序列化和反序列化二叉搜索树 | 中等 | BST可借助有序性减少结构标记，普通二叉树序列化需要显式保留形状。 |
| 331. 验证二叉树的前序序列化 | 中等 | 同样依赖空节点标记表达结构，原题只验证前序编码，本题还需从编码重建树。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！