如何序列化和反序列化一棵二叉树？

简化版

序列化是把二叉树转成字符串，反序列化是从字符串还原树。常见做法是前序遍历加空指针标记，例如 1,2,#,#,3,#,#，反序列化时按同样顺序递归消费 token，时间 O(n)，空间 O(n)。

详细版

如果只保存非空节点，树结构会丢失；必须保存空指针或使用能唯一确定结构的编码。前序 + # 是最经典方案：序列化时先写当前节点，再写左子树、右子树；反序列化时读到 # 返回 null，否则创建节点并递归构造左右子树。

String serialize(TreeNode root) {
    StringBuilder sb = new StringBuilder();
    encode(root, sb);
    return sb.toString();
}

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

反序列化时要使用队列或下标指针按顺序消费，不能每层重新扫描字符串。

完整版教学

一、为什么序列化必须保留结构信息

二叉树不是普通数组，只有节点值无法还原左右孩子关系。比如前序遍历 1,2,3 可以对应多棵不同的树：可能 2 是左孩子，也可能是右孩子；3 也可能挂在不同位置。序列化的核心不是“把值打印出来”，而是把空孩子位置也编码进去。

树 A:      1          树 B:      1
          /                      \
         2                        2
        /                          \
       3                            3

两棵树的非空前序都是 1,2,3，但结构完全不同。加入空指针标记后，它们的编码就会不同。

二、前序 + 空标记为什么能唯一还原

前序遍历的顺序是“根、左、右”。如果遇到空节点也写入 #，那么每个子树都会形成一段完整编码：第一个 token 是子树根，后面紧跟它的左子树编码和右子树编码。反序列化时也按这个顺序递归读取，就能知道每个节点的左右边界。

    1
   / \
  2   3

前序含空: 1,2,#,#,3,#,#

读到 1 创建根；读到 2 创建左子树；接下来两个 # 表示 2 的左右孩子为空；然后读到 3 创建右子树。整个过程不需要额外查找根位置。

三、反序列化为什么要“按顺序消费”

反序列化不能把 token 当成随机访问数组随便跳。递归函数的语义是：从当前 token 开始，还原一棵子树，并把这棵子树消耗掉的 token 全部推进。用队列最直观，因为每次只取队头。

TreeNode decode(Queue<String> q) {
    String x = q.poll();
    if (x.equals("#")) return null;
    TreeNode node = new TreeNode(Integer.parseInt(x));
    node.left = decode(q);
    node.right = decode(q);
    return node;
}

这个代码看起来短，是因为编码规则已经保证了“每个节点后面都有完整左右子树”。如果序列化和反序列化顺序不一致，必然还原错误。

四、层序序列化也常见，但要处理尾部空节点

层序编码按照队列从上到下、从左到右输出节点。它更接近数组表示，适合和前端/接口交互，但会产生很多空节点标记。为了减少字符串长度，通常可以去掉末尾连续的 #，因为尾部空孩子不会再影响结构。

方案	编码例子	优点	注意点
前序 + #	`1,2,#,#,3,#,#`	递归还原简单	深树可能递归很深
层序 + #	`1,2,3,#,#,#,#`	接近数组格式	尾部空标记可裁剪
前序 + 中序	两个序列	无空标记	要求节点值可区分

面试里如果没有指定格式，前序 + 空标记最容易写对，也最容易解释清楚。

五、复杂度和工程边界

序列化要访问每个非空节点和空指针位置。对 n 个非空节点的二叉树，空指针数量是 n + 1，所以 token 总数约 2n + 1，时间和空间都是 O(n)。这个数字也说明为什么空标记不是小细节，而是结构信息本身。

n 个节点
非空 token = n
空指针 token = n + 1
总 token = 2n + 1

工程里还要考虑分隔符、负数、重复值、空字符串和非法输入。节点值可能为负，所以不要用 - 当特殊空标记；分隔符也要选择不会和数字混淆的字符。

六、常见误区与追问

记忆钩子：序列化不是保存遍历结果，而是保存“遍历结果 + 空位”，空位才让结构可逆。

误区：只保存前序遍历就能还原。 只有值没有空位，无法区分不同结构。
误区：反序列化时可以先构造所有节点再连边。 前序含空编码的边界来自顺序消费，先建所有节点反而会丢失子树边界。
误区：重复值会影响前序加空标记。 不影响，因为空标记已经确定结构，不靠值查位置。
追问：为什么空指针数量是 n+1？ 二叉树有 2n 个孩子指针，真实边有 n-1 条，所以空指针是 2n-(n-1)=n+1。
追问：层序编码怎么减少长度？ 可以删除末尾连续空标记，因为它们不再承载后续非空节点的位置。
追问：怎样校验反序列化输入合法？ 可检查 token 是否被刚好消费完、数字解析是否成功、空树格式是否符合约定。

七、加强记忆

把序列化记成“给树拍 X 光”：节点值是骨架，空指针是关节空位。只看骨架编号无法知道左右关系，必须把空位也拍进去。前序写入时根先出现，反序列化时按同样顺序消费，读到值就建节点，读到 # 就返回 null，这样编码和解码天然互为镜像。

简化版

详细版