LeetCode 297. 二叉树的序列化与反序列化

2026-05-25 HGNULB 约 5 分钟

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

分类

LeetCode CodeTop 困难已解决 50-100 字节跳动微软美团阿里巴巴快手腾讯猿辅导拼多多小米虾皮

题目描述

✅ 297. 二叉树的序列化与反序列化

题意分析

要求设计一对方法：serialize 把二叉树编码成字符串，deserialize 把这个字符串还原成结构完全相同的树。题目明确说明不限定编码格式，也不要求遵循 LeetCode 的输入表示——只要自己写出的串自己能还原即可，格式是完全自由的设计空间。

约束信号：节点数最多 $10^4$，节点值范围 [-1000, 1000]——值可能是负数、可能是多位数，编码时必须能区分每个值的边界；不同节点的值还可能相同，所以值本身不能当身份标识，能依赖的只有「值 + 结构」的完整信息。

边界：空树也要能编码、能还原；单节点树，以及只有左链或只有右链的退化树，都不能丢失形状信息。

解法：前序遍历记录空节点

核心思路

问题关键：只记录前序节点值会丢失结构。例如 2 是根的左孩子还是右孩子，值序列都可能是 1,2；节点值还可能重复，不能靠值定位边界。

为什么选“前序 + 空节点标记”：把空指针编码成 # 后，每棵子树都表示为“根、左子树、右子树”，结构边界被完整保留。反序列化按相同顺序消费 token，遇到值就建节点，遇到 # 就返回空，代码与定义完全对称。

不变量与正确性：每次进入 build 时，游标都指向当前待构造子树的根 token。消费根后递归构造左、右子树；左子树恰好消费自己的完整编码，所以返回时游标自然落在右子树开头。归纳可得每棵子树都被唯一还原。

解题步骤

序列化采用前序遍历：非空节点写入数值，空节点写入 #，token 之间用逗号分隔。

反序列化先按逗号切分，并把共享游标重置到 0。

读取一个 token：若为 #，当前子树为空；否则创建根节点。

按序递归构造根的左子树和右子树，并返回根节点。

例如根 1 只有左孩子 2，编码为 1,2,#,#,#；三个 # 分别封住 2 的左右孩子和 1 的右孩子，结构没有歧义。

代码实现

public class Codec {
    private int index;

    public String serialize(TreeNode root) {
        StringBuilder builder = new StringBuilder();
        encode(root, builder);
        builder.setLength(builder.length() - 1);
        return builder.toString();
    }

    private void encode(TreeNode node, StringBuilder builder) {
        if (node == null) {
            builder.append("#,");
            return;
        }
        builder.append(node.val).append(',');
        encode(node.left, builder);
        encode(node.right, builder);
    }

    public TreeNode deserialize(String data) {
        index = 0;
        return build(data.split(","));
    }

    private TreeNode build(String[] tokens) {
        String token = tokens[index++];
        if ("#".equals(token)) {
            return null;
        }
        TreeNode node = new TreeNode(Integer.parseInt(token));
        node.left = build(tokens);
        node.right = build(tokens);
        return node;
    }
}

type Codec struct{}

func Constructor() Codec {
    return Codec{}
}

func (this *Codec) serialize(root *TreeNode) string {
    values := make([]string, 0)

    var dfs func(*TreeNode)
    dfs = func(node *TreeNode) {
        if node == nil {
            values = append(values, "#")
            return
        }

        values = append(values, strconv.Itoa(node.Val))
        dfs(node.Left)
        dfs(node.Right)
    }

    dfs(root)
    return strings.Join(values, ",")
}

func (this *Codec) deserialize(data string) *TreeNode {
    tokens := strings.Split(data, ",")
    idx := 0

    var build func() *TreeNode
    build = func() *TreeNode {
        token := tokens[idx]
        idx++
        if token == "#" {
            return nil
        }

        value, _ := strconv.Atoi(token)
        node := &TreeNode{Val: value}
        node.Left = build()
        node.Right = build()
        return node
    }

    return build()
}

复杂度分析

时间复杂度：$O(n)$，含 $n$ 个节点的二叉树恰有 $n+1$ 个空指针，共处理 2n+1 个 token。

空间复杂度：$O(n)$，编码串和切分后的 token 数组为线性空间；递归栈为 $O(h)$，最坏链状树时 $h=n$。

关键点总结

空节点标记补全的是树的结构信息，因此不要求节点值互异。

序列化和反序列化必须使用相同遍历顺序；前序的优势是读到根后可以立即建树。

游标必须跨递归共享，并在每次 deserialize 开始时重置。

层序编码也可行，但前序递归更短、更对称，适合作为面试主解法。

易错点总结

不记录空节点：左孩子树 [1,2] 与右孩子树 [1,null,2] 都会得到 1,2，无法还原。

写入顺序和读取顺序不同：前序编码却先构造右子树，会把整棵树接反。

Java 用 token == "#" 比较字符串：可能把 # 当整数解析，应使用 "#".equals(token)。

忘记在 deserialize 开头重置成员游标：同一个 Codec 第二次调用会从数组末尾继续读。

空树编码为空串：反序列化会尝试解析 ""；统一编码成 # 可避免额外分支。

相似题目

题目	难度	考察点
449. 序列化和反序列化二叉搜索树	中等	BST 可利用有序性省去占位符，用值域上下界还原
105. 从前序与中序遍历序列构造二叉树	中等	用前序 + 中序双序列定位子树边界，要求节点值互异
331. 验证二叉树的前序序列化	中等	只验证序列合法性不重建，用槽位（出入度）计数
428. 序列化和反序列化 N 叉树	困难	孩子数不固定，需额外编码孩子个数或结束标记
剑指 Offer 37. 序列化二叉树	困难	同题镜像，常用层序 + 队列实现，可对照两种遍历序
LCR 048. 二叉树的序列化与反序列化	困难	同题变体，练习自定义占位符与分隔符的编码设计