我来给你讲解 LeetCode 第 297 题「二叉树的序列化与反序列化」。

题目描述

设计一个算法，将二叉树序列化为一个字符串，并且可以将字符串反序列化为原始的二叉树结构。序列化/反序列化的算法需要保证二叉树能够被唯一地还原。

解题思路

核心思想

我们需要选择一种遍历方式（如前序、中序、后序或层序）来将二叉树转换为字符串，然后用同样的遍历逻辑将字符串还原为二叉树。

为什么需要特殊处理空节点？

如果只记录非空节点的值，不同的二叉树可能产生相同的序列化结果。因此我们需要用特殊标记（如"null"）来表示空节点，这样才能唯一确定二叉树的结构。

详细解题步骤

方法一：前序遍历法（推荐）

序列化过程（二叉树 → 字符串）

1. 递归前序遍历：按照"根节点-左子树-右子树"的顺序遍历
2. 处理当前节点：
   • 如果当前节点为空，在字符串中添加"null"标记
   • 如果当前节点非空，在字符串中添加节点值
3. 分隔符：用逗号分隔每个节点的值

示例：二叉树 [1,2,3,null,null,4,5]

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

反序列化过程（字符串 → 二叉树）

1. 字符串分割：将序列化字符串按逗号分割成节点值列表
2. 递归构建：
   • 从列表头部取出一个值
   • 如果值是"null"，返回空节点
   • 否则用该值创建新节点，递归构建左右子树
3. 注意顺序：构建顺序要与序列化顺序一致（根→左→右）

方法二：层序遍历法

序列化过程

1. 使用队列进行层序遍历
2. 将每个节点（包括空节点）的值按顺序加入结果
3. 遇到空节点时添加"null"标记

示例：同样的二叉树 [1,2,3,null,null,4,5]

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

反序列化过程

1. 将字符串分割成节点值列表
2. 用队列辅助构建二叉树：
   • 创建根节点并入队
   • 每次从队列取出节点，为其添加左右子节点
   • 将新创建的非空子节点入队

代码实现（前序遍历法）

class Codec:
    def serialize(self, root):
        """将二叉树序列化为字符串"""
        def preorder(node):
            if not node:
                return "null"
            # 根节点值 + 左子树序列化 + 右子树序列化
            return str(node.val) + "," + preorder(node.left) + "," + preorder(node.right)
        
        return preorder(root)

    def deserialize(self, data):
        """将字符串反序列化为二叉树"""
        nodes = data.split(",")
        self.index = 0  # 全局索引，记录当前处理的位置
        
        def build_tree():
            if self.index >= len(nodes) or nodes[self.index] == "null":
                self.index += 1
                return None
            
            # 创建当前节点
            node = TreeNode(int(nodes[self.index]))
            self.index += 1
            
            # 递归构建左右子树
            node.left = build_tree()
            node.right = build_tree()
            
            return node
        
        return build_tree()

关键要点解析

1. 唯一性保证：通过记录空节点，确保二叉树结构唯一
2. 分隔符选择：逗号分隔便于分割，避免数字位数问题
3. 递归同步：序列化和反序列化使用相同的遍历顺序
4. 索引管理：反序列化时需要全局索引来跟踪处理进度

复杂度分析

• 时间复杂度：O(n)，每个节点访问一次
• 空间复杂度：O(n)，递归栈空间或队列空间

这种方法可以处理任意形状的二叉树，保证序列化和反序列化的正确性。