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

二叉树序列化是将二叉树结构转换为字符串表示的过程，反序列化则是将字符串恢复为原始二叉树结构的过程。这个知识点在面试中经常出现，因为它考察了对二叉树遍历、数据结构和字符串处理的综合理解。

1. 问题描述
给定一个二叉树的根节点，要求实现两个函数：

• serialize(root)：将二叉树序列化为字符串
• deserialize(data)：将字符串反序列化为二叉树

序列化后的字符串应该包含足够的信息，能够唯一确定原始的二叉树结构。

2. 设计思路
我们需要选择一种遍历顺序来序列化二叉树。常见的选择有前序遍历、中序遍历、后序遍历和层序遍历。

前序遍历方案的优势：

• 序列化时第一个元素就是根节点，便于反序列化时重建
• 实现相对简单直观

特殊考虑：

• 需要处理空节点，通常用特殊标记（如"null"或"#"）表示
• 需要分隔符来区分不同节点的值

3. 序列化实现（前序遍历）

步骤分解：

1. 创建结果列表，用于存储序列化后的节点值
2. 定义递归辅助函数，按前序遍历顺序处理节点
3. 如果当前节点为空，将空标记加入结果列表
4. 如果当前节点非空，将节点值加入结果列表，然后递归处理左右子树
5. 将结果列表用分隔符连接成字符串

详细实现：

def serialize(root):
    result = []
    
    def preorder(node):
        if not node:
            result.append("null")  # 空节点标记
            return
        result.append(str(node.val))  # 当前节点值
        preorder(node.left)          # 递归左子树
        preorder(node.right)         # 递归右子树
    
    preorder(root)
    return ",".join(result)  # 用逗号分隔

示例说明：
对于二叉树：

    1
   / \
  2   3
     / \
    4   5

序列化结果为："1,2,null,null,3,4,null,null,5,null,null"

4. 反序列化实现

核心思路：

• 按前序遍历顺序重建二叉树
• 每次从序列化字符串中取出一个元素
• 如果是空标记，返回空节点
• 如果是数字，创建节点，然后递归构建左右子树

步骤分解：

1. 将序列化字符串按分隔符拆分为节点值列表
2. 定义递归函数，按前序遍历顺序重建二叉树
3. 每次从列表中取出第一个元素
4. 如果是空标记，返回None并移动到下一个元素
5. 如果是数字，创建节点，递归构建左右子树
6. 返回重建的二叉树

详细实现：

def deserialize(data):
    nodes = data.split(",")  # 拆分节点值
    nodes_iter = iter(nodes)  # 创建迭代器便于顺序访问
    
    def build_tree():
        val = next(nodes_iter)  # 获取下一个节点值
        if val == "null":
            return None
        node = TreeNode(int(val))      # 创建当前节点
        node.left = build_tree()       # 递归构建左子树
        node.right = build_tree()      # 递归构建右子树
        return node
    
    return build_tree()

5. 算法分析

时间复杂度：

• 序列化：O(n)，每个节点访问一次
• 反序列化：O(n)，每个节点处理一次

空间复杂度：

• 序列化：O(n)，递归栈深度和结果存储
• 反序列化：O(n)，递归栈深度和节点列表存储

6. 其他序列化方案

层序遍历方案：

from collections import deque

def serialize_levelorder(root):
    if not root:
        return ""
    
    result = []
    queue = deque([root])
    
    while queue:
        node = queue.popleft()
        if node:
            result.append(str(node.val))
            queue.append(node.left)
            queue.append(node.right)
        else:
            result.append("null")
    
    return ",".join(result)

7. 注意事项

• 分隔符选择：确保节点值中不包含分隔符字符
• 空节点处理：必须明确标记空节点，否则无法重建唯一二叉树
• 数值类型：如果节点值不是整数，需要相应调整序列化格式
• 边界情况：空树的序列化结果应为空字符串或只包含空标记

8. 实际应用

• 数据持久化：将内存中的树结构保存到文件或数据库
• 网络传输：在不同系统间传输树结构数据
• 测试用例：便于生成和验证二叉树相关的测试数据

通过这种序列化方法，我们可以有效地在字符串形式和二叉树结构之间进行转换，这在很多实际应用场景中都非常有用。