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

2026-05-25 HGNULB 约 6 分钟

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

分类

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

题目描述

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

题意分析

设计成对的两个操作：serialize 把二叉树转成字符串，deserialize 根据该字符串重新创建一棵树。还原后的节点值、左右孩子关系都必须与原树一致，不能只得到相同的节点值集合。

字符串格式可以自行设计，不必照搬题面展示的数组格式。节点值可能重复、可能为负，树也可能为空；反序列化读取的是本方案产生的合法编码，不要求处理任意损坏的字符串。

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

核心思路

[!blue]

仅按遍历顺序记录非空节点的值，会丢失左右孩子是否存在的信息。采用前序顺序“根、左子树、右子树”，并用 # 表示空子树，就能同时保存值和结构。每个数值或空标记之间用逗号分隔，避免多位数和负数的边界产生歧义。

一棵子树的编码规则只有两种：空树写一个 #；非空树先写根的数值，再完整写出左子树和右子树。序列化递归严格按这个规则进行，空树也会产生一个标记，因此始终有内容可输出。

反序列化按相同规则读数据。build 每次先读一个标记：读到 # 就返回空；否则创建根，再递归读完左子树、右子树。一次调用恰好消耗一棵子树的完整编码，所以左子树返回时，游标自然已经来到右子树的开头，不需要提前计算两棵子树的长度。

所有递归层共享同一个读取位置，且每次反序列化都从零开始。遇到空标记就确定一条孩子边为空，遇到数值就确定一个节点和它的两个孩子位置，因此即使数值重复，整棵树的还原也没有歧义。

解题步骤

从根节点开始前序编码：非空节点追加数值，再递归处理左右子树；空节点追加 #。

将全部标记用逗号连接。Java 逐个追加分隔符，最后去掉末尾逗号；Go 使用 strings.Join 连接标记列表。

反序列化先按逗号切分编码，并将共享读取游标置为 0。

build 读取当前标记并推进游标；若是 #，返回空节点。

否则将标记解析为整数、创建节点，依次调用 build 连接左、右孩子，最后返回该节点。最外层返回值就是还原后的根。

代码实现

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

import (
    "strconv"
    "strings"
)

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)$。非空节点有 2n 个孩子位置，其中 n-1 个连着真实节点，其余 n+1 个为空，所以总共处理 2n+1 个标记；空树则单独产生一个 #。题目中的整数位数有固定上界。

空间复杂度：$O(n)$。编码缓冲、标记列表或切分数组占用线性空间，递归栈为 $O(h)$，h 是树高；链状树时可达到 $O(n)$。反序列化创建的新树还需要 $O(n)$ 输出空间。

关键点总结

[!green]

数值记录节点内容，空标记记录孩子位置，两者一起才能还原普通二叉树。

写入与读取遵循同一种递归结构，一次 build 消费一整棵子树。

游标跨递归层共享，但不能跨两次独立反序列化沿用旧位置。

标记之间明确分隔，使重复值、多位数和负数都不影响结构解析。

易错点总结

[!yellow]

省略空节点，只剩数值序列时无法判断孩子在左边还是右边，也无法确定子树边界。

写入时先左后右，读取时却颠倒顺序，会改变原树的孩子关系。

各层使用独立且不回传的游标，会重复读取同一段数据；消费位置必须被后续递归接着使用。

Java 忘记在每次 deserialize 开始时重置成员游标，同一个对象第二次读取会从错误位置开始。

Java 用 == 比较字符串内容，可能无法识别空标记，应使用 "#".equals(token)。

空树编码为空串却仍按整数标记解析，会失败；本方案统一用 # 表达空树，无需额外格式。

相似题目

题目	难度	关联与区别
449. 序列化和反序列化二叉搜索树	中等	BST可借助有序性减少结构标记，普通二叉树序列化需要显式保留形状。
331. 验证二叉树的前序序列化	中等	同样依赖空节点标记表达结构，原题只验证前序编码，本题还需从编码重建树。

.article-image.is-loading { width: var(--article-image-width, 100%); height: auto; } .article-image.is-loading img { position: static; width: auto !important; height: auto !important; opacity: 1; pointer-events: auto; } .article-image-spinner { display: none; }

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2026/53391298

许可本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！