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

二叉树的序列化与反序列化是指将二叉树结构转换为一个字符串（或字节序列）以便存储或传输，并能从该字符串准确重建原二叉树的过程。这是处理树结构数据持久化和网络传输的基础技术。

一、问题描述与核心挑战

问题描述：
设计两个函数：

1. serialize(root)：将二叉树root转换为一个字符串。
2. deserialize(data)：将字符串data还原为原始的二叉树结构。

核心挑战：

• 序列化后的字符串必须包含足够的信息，确保反序列化能唯一确定原树的结构。
• 需要高效处理空节点，以明确树的形状。
• 序列化结果应尽量紧凑，减少存储和传输开销。

二、序列化策略：前序遍历与空节点表示

1. 选择遍历方式
前序遍历（根-左-右）是直观的选择，因为反序列化时能首先确定根节点，便于递归重建。其他遍历方式（如层次遍历）也可行，但前序遍历实现简洁。

2. 表示空节点
用特殊符号（如"null"或"#"）标记空节点，确保树结构唯一性。例如，叶子节点的左右空子节点都需显式标记。

3. 分隔符选择
使用分隔符（如逗号,）分隔节点值，便于反序列化时切分字符串。

示例：
二叉树：

    1
   / \
  2   3
     / \
    4   5

前序遍历序列化结果："1,2,null,null,3,4,null,null,5,null,null"。

三、序列化实现步骤

步骤1：递归前序遍历

• 访问根节点，将其值加入字符串。
• 递归处理左子树，若左子树为空则添加"null"。
• 递归处理右子树，若右子树为空则添加"null"。

步骤2：边界处理

• 若根节点为空，直接返回"null"。
• 使用StringBuilder或类似结构高效拼接字符串，避免频繁创建新字符串。

代码示例（Java）：

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

private void buildString(TreeNode node, StringBuilder sb) {
    if (node == null) {
        sb.append("null,");
    } else {
        sb.append(node.val).append(",");
        buildString(node.left, sb);
        buildString(node.right, sb);
    }
}

四、反序列化实现步骤

步骤1：字符串解析

• 将序列化字符串按分隔符切分为节点值列表（如数组或队列）。
• 使用队列（先进先出）顺序处理节点值，与前序遍历顺序一致。

步骤2：递归重建二叉树

• 从队列头部取出一个值，若为"null"则返回空节点。
• 否则，以该值创建根节点，并递归构建左子树和右子树。

代码示例（Java）：

public TreeNode deserialize(String data) {
    Queue<String> nodes = new LinkedList<>(Arrays.asList(data.split(",")));
    return buildTree(nodes);
}

private TreeNode buildTree(Queue<String> nodes) {
    String val = nodes.poll();
    if (val.equals("null")) return null;
    TreeNode node = new TreeNode(Integer.parseInt(val));
    node.left = buildTree(nodes);
    node.right = buildTree(nodes);
    return node;
}

五、复杂度与优化分析

时间复杂度：

• 序列化和反序列化均需访问每个节点一次，时间复杂度为 O(n)。

空间复杂度：

• 递归调用栈深度为树高，平均 O(log n)，最坏（链状树）O(n)。
• 序列化字符串空间为 O(n)。

优化方向：

1. 压缩表示：用单字符（如"#"）代替"null"，减少字符串长度。
2. 迭代实现：用显式栈替代递归，避免栈溢出风险。
3. 二进制序列化：直接编码为二进制格式，进一步提升效率（但可读性差）。

六、其他序列化方法对比

1. 层次遍历序列化

   • 使用队列按层序列化，空节点也需标记。
   • 反序列化时需维护父子关系队列，实现稍复杂但易于理解。
   • 示例："1,2,3,null,null,4,5,null,null,null,null"。

2. 括号表示法

   • 形如"1(2()())(3(4()())(5()()))"，通过括号嵌套表示结构。
   • 无需显式空节点标记，但字符串较长。

七、应用场景

• 持久化存储：将二叉树保存到文件或数据库。
• 网络传输：在分布式系统中发送树结构数据。
• 测试用例：序列化字符串可作为单元测试的输入输出标准。

通过以上步骤，你可以完整掌握二叉树序列化与反序列化的原理、实现及优化方法，灵活应用于实际问题中。