二叉树的序列化与反序列化

序列化是将二叉树转化为可存储 / 传输的字符串，反序列化是将字符串还原为二叉树。关键是选择合适的遍历方式，并用特殊标记表示空节点。

三种常见序列化方式

遍历方式	序列化序列	适用场景
前序遍历	根 → 左 → 右	最常用，LeetCode 297
层序遍历	逐层从左到右	直观，BFS 实现
后序遍历	左 → 右 → 根	较少单独使用

空节点标记

必须用特殊符号（如 # 或 null）标记空子树，否则无法唯一还原。

序列化：1,2,#,#,3,4,#,#,5,#,#
反序列化时遇到 # 就知道该位置无节点

序列化过程

function serialize(root):
    if root == null:
        return "#,"
    result = root.val + ","
    result += serialize(root.left)
    result += serialize(root.right)
    return result

示例二叉树：

        1
       / \
      2   3
         / \
        4   5

前序序列化结果：1,2,#,#,3,4,#,#,5,#,#

反序列化过程

function deserialize(data):
    nodes = data.split(",")  → ["1","2","#","#","3","4","#","#","5","#","#"]
    index = 0（全局指针）

    function build():
        val = nodes[index]
        index++
        if val == "#":
            return null
        node = new TreeNode(val)
        node.left  = build()    // 递归构建左子树
        node.right = build()    // 递归构建右子树
        return node

    return build()

序列化（BFS）

对上面同一棵示例树：

序列化结果：1,2,3,#,#,4,5,#,#,#,#

逐层遍历，空节点也写入结果（用 # 标记），直到队列中不再有真实节点。

反序列化（BFS）

nodes = ["1","2","3","#","#","4","5","#","#","#","#"]
         i=0  i=1  i=2  i=3  i=4  i=5  i=6  ...

root = TreeNode(1), 入队
取出 1: 左孩子=nodes[1]=2, 右孩子=nodes[2]=3, 入队
取出 2: 左孩子=nodes[3]=#, 右孩子=nodes[4]=#（跳过）
取出 3: 左孩子=nodes[5]=4, 右孩子=nodes[6]=5, 入队
取出 4: 左孩子=nodes[7]=#, 右孩子=nodes[8]=#（跳过）
取出 5: 左孩子=nodes[9]=#, 右孩子=nodes[10]=#（跳过）
完成

例题 1：前序序列化

题目：对以下二叉树进行前序序列化。

        A
       / \
      B   C
     /   / \
    D   E   F

序列化过程（前序：根 → 左 → 右）：

步骤	访问节点	输出	说明
1	A	A,	根节点
2	B	A,B,	A 的左孩子
3	D	A,B,D,	B 的左孩子
4	D.left = #	A,B,D,#,	D 无左孩子
5	D.right = #	A,B,D,#,#,	D 无右孩子
6	B.right = #	A,B,D,#,#,#,	B 无右孩子
7	C	…,C,	A 的右孩子
8	E	…,C,E,	C 的左孩子
9	E.left = #	…,C,E,#,	E 无左孩子
10	E.right = #	…,C,E,#,#,	E 无右孩子
11	F	…,E,#,#,F,	C 的右孩子
12	F.left = #	…,F,#,	F 无左孩子
13	F.right = #	…,F,#,#	F 无右孩子

最终结果：A,B,D,#,#,#,C,E,#,#,F,#,#

校验长度：$2n+1 = 2\times 6 + 1 = 13$ 个元素 ✓（6 个真实节点 + 7 个 #）。

例题 2：层序序列化

同一棵树，按完全二叉树下标思路排布（结点 $i$ 的左右孩子在 $2i+1$、$2i+2$）：

nodes = [A, B, C, D, #, E, F, #, #, #, #, #, #]
下标      0  1  2  3  4  5  6

结果：A,B,C,D,#,E,F,#,#,#,#,#,#