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

题目描述

序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。

请你设计一个算法来实现二叉树的序列化与反序列化。

这里的意思其实很简单：

序列化：把一棵二叉树转成字符串
反序列化：把字符串再还原成原来的二叉树

你给出的这份代码采用的是 层序遍历（BFS） 的做法，这也是非常经典、非常直观的一种实现方式。

这道题的核心难点

这道题看起来像是在考字符串处理，其实真正考察的是：

如何完整保留一棵二叉树的结构信息。

因为仅仅记录节点值是不够的。

比如下面两棵树：

树 1

    1
   /
  2

树 2

    1
     \
      2

它们的节点值都是 1, 2，但结构不同。

所以如果我们只记录值：

[1,2]

是无法区分这两棵树的。

因此在序列化时，必须把空节点也记录下来。也就是你代码里写的：

null

这样才能保证：

值信息 + 结构信息 都被保留下来。

为什么层序遍历适合这题

你这份代码使用的是层序遍历，也就是按“从上到下、从左到右”的顺序去处理节点。

这种做法有两个好处：

1. 序列化直观

我们一边 BFS，一边把每个节点写进字符串：

节点存在，就写它的值
节点为空，就写 null

这样就能把整棵树完整展开成一个类似数组的形式。

例如：

会被写成：

[1,2,3,null,null,4,5,null,null,null,null]

2. 反序列化方便

有了这种层序字符串后，我们就可以按照同样的 BFS 顺序，把节点一层层重新连回去。

也就是说：

队列里保存当前还没分配左右孩子的节点
每次从字符串里取两个值，分别作为当前节点的左孩子、右孩子

这样还原过程非常自然。

你的代码

public class Codec {
    public String serialize(TreeNode root) {
        if (root == null) return "[]";
        StringBuilder res = new StringBuilder("[");
        Queue<TreeNode> queue = new LinkedList<>() {{ add(root); }};
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (node != null) {
                res.append(node.val + ",");
                queue.add(node.left);
                queue.add(node.right);
            }
            else res.append("null,");
        }
        res.deleteCharAt(res.length() - 1);
        res.append("]");
        return res.toString();
    }

    public TreeNode deserialize(String data) {
        if (data.equals("[]")) return null;
        String[] vals = data.substring(1, data.length() - 1).split(",");
        TreeNode root = new TreeNode(Integer.parseInt(vals[0]));
        Queue<TreeNode> queue = new LinkedList<>() {{ add(root); }};
        int i = 1;
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (!vals[i].equals("null")) {
                node.left = new TreeNode(Integer.parseInt(vals[i]));
                queue.add(node.left);
            }
            i++;
            if (!vals[i].equals("null")) {
                node.right = new TreeNode(Integer.parseInt(vals[i]));
                queue.add(node.right);
            }
            i++;
        }
        return root;
    }
}

这份写法很标准，整体可以分成两部分：

serialize：把树转成字符串
deserialize：把字符串还原成树

下面分别展开讲。

一、序列化 serialize

代码

public String serialize(TreeNode root) {
    if (root == null) return "[]";
    StringBuilder res = new StringBuilder("[");
    Queue<TreeNode> queue = new LinkedList<>() {{ add(root); }};
    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();
        if (node != null) {
            res.append(node.val + ",");
            queue.add(node.left);
            queue.add(node.right);
        }
        else res.append("null,");
    }
    res.deleteCharAt(res.length() - 1);
    res.append("]");
    return res.toString();
}

序列化整体思路

如果树为空，直接返回 "[]"
否则从根节点开始做层序遍历
每取出一个节点：
- 如果不为空，就记录它的值，并把左右孩子加入队列
- 如果为空，就记录 null
最后把结果拼成一个字符串返回

为什么空节点也要入队

这是序列化里最关键的一点。

看这段代码：

if (node != null) {
    res.append(node.val + ",");
    queue.add(node.left);
    queue.add(node.right);
}
else res.append("null,");

如果一个节点不为空，不仅要记录它的值，还要把它的左右孩子都入队。这里即使左孩子或右孩子为空，也照样入队。

为什么？

因为这样才能把树的结构完整保留下来。

例如：

    1
   /
  2

如果不把空右孩子记成 null，那反序列化时根本不知道 2 是左孩子还是右孩子。

所以必须把空位置也显式记录下来。

序列化示例推演

假设有这棵树：

初始状态

queue = [1]
res = "["

取出 1

记录：

res = "[1,"

把左右孩子入队：

queue = [2, 3]

取出 2

记录：

res = "[1,2,"

把 2 的左右孩子入队，它们都是空：

queue = [3, null, null]

取出 3

记录：

res = "[1,2,3,"

把 4、5 入队：

queue = [null, null, 4, 5]

继续处理 null、4、5 …

最终得到：

[1,2,3,null,null,4,5,null,null,null,null]

这就是这棵树的完整层序表示。

最后为什么要删掉最后一个逗号

res.deleteCharAt(res.length() - 1);

因为在循环中每次都会追加一个逗号，所以最后会多一个尾逗号。删掉之后再补上 ]，格式才是合法的字符串表示。

二、反序列化 deserialize

代码

public TreeNode deserialize(String data) {
    if (data.equals("[]")) return null;
    String[] vals = data.substring(1, data.length() - 1).split(",");
    TreeNode root = new TreeNode(Integer.parseInt(vals[0]));
    Queue<TreeNode> queue = new LinkedList<>() {{ add(root); }};
    int i = 1;
    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();
        if (!vals[i].equals("null")) {
            node.left = new TreeNode(Integer.parseInt(vals[i]));
            queue.add(node.left);
        }
        i++;
        if (!vals[i].equals("null")) {
            node.right = new TreeNode(Integer.parseInt(vals[i]));
            queue.add(node.right);
        }
        i++;
    }
    return root;
}

反序列化整体思路

反序列化时，我们已经有了一串层序遍历结果。

要做的事情就是：

先根据第一个值创建根节点
用一个队列保存“还没有分配左右孩子的节点”
每次从队列中取出一个节点
按顺序从数组中读两个值：
- 一个作为左孩子
- 一个作为右孩子
如果孩子不为空，就创建节点并加入队列
直到所有值都处理完

代码解析

1. 空树直接返回

if (data.equals("[]")) return null;

如果序列化结果就是空数组，说明原树为空。

2. 去掉方括号并切分字符串

String[] vals = data.substring(1, data.length() - 1).split(",");

例如：

"[1,2,3,null,null,4,5]"

会变成：

["1","2","3","null","null","4","5"]

这样就方便按顺序读取。

3. 创建根节点

TreeNode root = new TreeNode(Integer.parseInt(vals[0]));

第一个值一定是根节点的值。

4. 队列初始化

Queue<TreeNode> queue = new LinkedList<>() {{ add(root); }};

队列中存的是“还需要给它分配左右孩子的节点”。

5. 用指针 `i` 指向当前读取位置

int i = 1;

因为 vals[0] 已经用来创建根节点了，所以从 1 开始往后读。

6. 不断从队列中取节点，并补左右孩子

while (!queue.isEmpty()) {
    TreeNode node = queue.poll();

当前取出的 node，就是接下来要给它挂孩子的父节点。

7. 处理左孩子

if (!vals[i].equals("null")) {
    node.left = new TreeNode(Integer.parseInt(vals[i]));
    queue.add(node.left);
}
i++;

如果当前值不是 null，说明左孩子存在，就创建出来并入队。然后 i++，继续读下一个值。

8. 处理右孩子

if (!vals[i].equals("null")) {
    node.right = new TreeNode(Integer.parseInt(vals[i]));
    queue.add(node.right);
}
i++;

逻辑和左孩子一样。

反序列化示例推演

还是看这串数据：

[1,2,3,null,null,4,5]

切分后：

vals = ["1","2","3","null","null","4","5"]

第一步：创建根节点 1

root = 1
queue = [1]
i = 1

第二步：取出 1，补左右孩子

vals[1] = "2"，创建左孩子 2
vals[2] = "3"，创建右孩子 3

现在：

queue = [2,3]
i = 3

第三步：取出 2，补左右孩子

vals[3] = "null"，左孩子为空
vals[4] = "null"，右孩子为空

现在：

queue = [3]
i = 5

第四步：取出 3，补左右孩子

vals[5] = "4"，创建左孩子 4
vals[6] = "5"，创建右孩子 5

现在：

queue = [4,5]
i = 7

树就被逐步还原出来了。

为什么这种方法能正确还原结构

因为序列化时用的是层序遍历，反序列化时也严格按照层序遍历的顺序去恢复。

具体来说：

序列化时，某个节点的左孩子、右孩子是按顺序写进字符串的
反序列化时，某个节点的左孩子、右孩子又按同样顺序读回来

这就保证了结构一一对应。

所以这种方法本质上就是：

用 BFS 的访问顺序来编码，再用 BFS 的恢复顺序来解码。

复杂度分析

设树中有 n 个节点。

序列化时间复杂度

O(n)

每个节点（以及必要的空节点标记）都只会处理一次。

反序列化时间复杂度

O(n)

每个有效节点都只会创建和连接一次。

空间复杂度

O(n)

主要来自：

队列
序列化字符串
反序列化时的节点存储

这份写法的优点

你这份代码最大的优点就是：

1. 思路非常直观

序列化：按层展开
反序列化：按层恢复

整体逻辑很统一。

2. 容易调试和理解

字符串长得就像层序数组，读起来比较清楚：

[1,2,3,null,null,4,5]

不像某些递归先序写法那样需要配合递归边界去理解。

3. 结构保留完整

通过显式记录 null，保证了树的形状不会丢失。

和“前序递归写法”对比

这道题还有一种非常经典的做法：

前序遍历序列化
遇到空节点就记 null
反序列化时递归构造

前序递归写法的优点

实现也很经典
代码可能更短

当前 BFS 写法的优点

更直观
更适合从“层”的角度理解树的结构
和数组层序表示非常接近

所以你这份 BFS 方案是非常好的入门和面试写法。

总结

这道题的核心就在于：

不仅要保存节点值，还要保存空节点信息，才能唯一确定一棵二叉树。

而你这份代码采用的方案是：

用层序遍历把树展开成字符串
空节点用 null 记录
再按层序顺序一层层把树恢复出来

你可以把这题记成一句话：

序列化按层展开，反序列化按层回填。

这是一道非常经典的树结构设计题，只要把“为什么必须记录 null”和“为什么层序可以一层层还原”这两个点想明白，这题就彻底掌握了。