LeetCode 297：二叉树的序列化与反序列化

LeetCode 297：二叉树的序列化与反序列化

一、问题背景与核心挑战

在分布式系统、数据存储和网络传输中，我们经常需要将复杂的数据结构（如二叉树）转换为可存储或传输的格式，这一过程称为序列化；而从序列化后的格式还原出原始数据结构的过程则称为反序列化。

对于二叉树而言，核心挑战在于：

1. 结构唯一性：必须完整记录树的结构，包括空节点，否则不同的树可能产生相同的序列化结果，导致反序列化时无法唯一还原。
2. 效率平衡：在保证结构完整性的同时，兼顾序列化和反序列化的时间与空间效率。

例如，仅记录非空节点的序列 "1,2,3" 无法区分以下两棵树：

 1 1 / \ / 2 3 2 / 3 

因此，空节点的记录是实现唯一还原的关键。

二、核心思路：层序遍历（BFS）的直观实现

为了直观且高效地解决问题，我们选择**层序遍历（BFS）**作为核心方法，原因如下：

• 层序遍历按“从上到下、从左到右”的顺序访问节点，每个节点的左右子节点位置明确，便于构建和还原。
• 与LeetCode官方的二叉树输入格式完全一致，降低理解和调试成本。

核心思想

• 序列化：用队列模拟层序遍历，将每个节点（包括空节点）转换为字符串，空节点用 "null" 表示，最终拼接为逗号分隔的字符串。
• 反序列化：将字符串按逗号分割为数组，用队列模拟层序构建树，依次为每个节点分配左右子节点，空节点直接跳过。

三、序列化步骤详解

1. 初始化与队列处理

• 若根节点为空，直接返回 "null"。
• 初始化队列，将根节点入队。
• 初始化 StringBuilder 用于拼接结果。

2. 遍历与记录

• 从队列中取出节点：
  • 若节点为空，向结果中添加 "null,"。
  • 若节点非空，添加节点值，并将其左右子节点（无论是否为空）入队。
• 遍历结束后，移除结果末尾多余的逗号。

示例演示（示例1）

输入树：[1,2,3,null,null,4,5]
序列化过程：

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

四、反序列化步骤详解

1. 初始化与数组分割

• 若输入字符串为 "null"，直接返回 null。
• 将字符串按逗号分割为数组，得到所有节点的字符串表示。

2. 队列构建树

• 第一个元素为根节点的值，创建根节点并入队。
• 初始化索引 i=1，遍历队列：
  • 取出队首节点作为父节点。
  • 处理左子节点：若数组 i 位置不是 "null"，创建左子节点并入队，i++。
  • 处理右子节点：若数组 i 位置不是 "null"，创建右子节点并入队，i++。
• 遍历结束后，返回根节点。

示例演示（示例1）

输入字符串："1,2,3,null,null,4,5,null,null,null,null"
分割数组：["1","2","3","null","null","4","5","null","null","null","null"]
反序列化过程：

最终还原的树结构与输入完全一致。

五、完整代码实现（Java）

importjava.util.LinkedList;importjava.util.Queue;/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */publicclassCodec{// Encodes a tree to a single string.publicStringserialize(TreeNode root){if(root ==null){return"null";}Queue<TreeNode> queue =newLinkedList<>(); queue.offer(root);StringBuilder sb =newStringBuilder();while(!queue.isEmpty()){TreeNode node = queue.poll();if(node ==null){ sb.append("null,");}else{ sb.append(node.val).append(","); queue.offer(node.left); queue.offer(node.right);}}// 移除末尾多余的逗号if(sb.length()>0){ sb.setLength(sb.length()-1);}return sb.toString();}// Decodes your encoded data to tree.publicTreeNodedeserialize(String data){if(data ==null|| data.equals("null")){returnnull;}String[] parts = data.split(",");Queue<TreeNode> queue =newLinkedList<>();TreeNode root =newTreeNode(Integer.parseInt(parts[0])); queue.offer(root);int i =1;while(!queue.isEmpty()&& i < parts.length){TreeNode parent = queue.poll();// 处理左子节点if(!parts[i].equals("null")){TreeNode left =newTreeNode(Integer.parseInt(parts[i])); parent.left = left; queue.offer(left);} i++;// 处理右子节点if(i < parts.length &&!parts[i].equals("null")){TreeNode right =newTreeNode(Integer.parseInt(parts[i])); parent.right = right; queue.offer(right);} i++;}return root;}}// Your Codec object will be instantiated and called as such:// Codec ser = new Codec();// Codec deser = new Codec();// TreeNode ans = deser.deserialize(ser.serialize(root));

六、思路延申：前序遍历的递归实现

除了层序遍历，前序遍历（DFS） 也是一种常见的序列化方式，其核心是“根-左-右”的递归顺序，空节点同样用 "null" 表示。

前序序列化

publicStringserializePre(TreeNode root){if(root ==null){return"null";}return root.val +","+serializePre(root.left)+","+serializePre(root.right);}

前序反序列化

importjava.util.Arrays;importjava.util.LinkedList;importjava.util.Queue;publicTreeNodedeserializePre(String data){Queue<String> queue =newLinkedList<>(Arrays.asList(data.split(",")));returnbuildTree(queue);}privateTreeNodebuildTree(Queue<String> queue){String val = queue.poll();if(val.equals("null")){returnnull;}TreeNode node =newTreeNode(Integer.parseInt(val)); node.left =buildTree(queue); node.right =buildTree(queue);return node;}

两种方法的对比

七、复杂度分析

• 时间复杂度：序列化和反序列化均为 (O(n))，每个节点仅处理一次，队列操作均摊为 (O(1))。
• 空间复杂度：序列化和反序列化均为 (O(n))，队列最多存储 (n) 个节点（最坏情况为完全二叉树的最后一层）。

八、总结与应用场景

二叉树的序列化与反序列化是数据结构与算法中的经典问题，其核心在于完整记录结构信息，确保唯一还原。在实际应用中：

• 层序遍历适合大数据流和分布式场景，非递归实现避免了栈溢出风险。
• 前序遍历适合算法题和教学场景，递归结构清晰，便于理解树的性质。

无论选择哪种方法，只要保证空节点的记录和遍历顺序的一致性，就能实现高效且可靠的序列化与反序列化。