知序
返回
保存草稿
发布
H1
H2
H3
1
2
3
Excalidraw 图
AI 写作
AI 优化
目录
输入内容后显示目录
Markdown
# 10 - 二叉树的序列化与反序列化 ## 题目(LeetCode 297) 设计一个算法,将二叉树序列化为字符串,并能将字符串反序列化为原始二叉树。 ``` 1 / \ 2 3 / \ 4 5 序列化: "1,2,#,#,3,4,#,#,5,#,#" 反序列化:还原为上面的树 ``` ## 大白话理解 序列化就是把一棵树"拍平"成一个字符串,方便存储或传输。反序列化就是从字符串还原出树。 关键问题:普通的前序遍历 `[1,2,3,4,5]` 无法唯一确定一棵树(你不知道哪些位置是空的)。 解决办法:把空节点也记录下来,用 `#` 表示。这样前序遍历就能唯一确定一棵树了。 ``` 1 / \ 2 3 / \ 4 5 前序遍历(含空节点):1, 2, #, #, 3, 4, #, #, 5, #, # 还原过程: 读到 1 → 创建节点 1 读到 2 → 创建节点 2(1 的左孩子) 读到 # → 2 的左孩子为空 读到 # → 2 的右孩子为空 读到 3 → 创建节点 3(1 的右孩子) 读到 4 → 创建节点 4(3 的左孩子) 读到 # → 4 的左孩子为空 读到 # → 4 的右孩子为空 读到 5 → 创建节点 5(3 的右孩子) 读到 # → 5 的左孩子为空 读到 # → 5 的右孩子为空 ``` ## 代码 ```java public class Codec { // 序列化:前序遍历,空节点用 "#" 表示 public String serialize(TreeNode root) { if (root == null) return "#"; return root.val + "," + serialize(root.left) + "," + serialize(root.right); } // 反序列化:按前序顺序依次取出节点 public TreeNode deserialize(String data) { Queue<String> queue = new LinkedList<>(Arrays.asList(data.split(","))); return buildTree(queue); } private TreeNode buildTree(Queue<String> queue) { String val = queue.poll(); if ("#".equals(val)) return null; TreeNode node = new TreeNode(Integer.parseInt(val)); node.left = buildTree(queue); // 递归构建左子树 node.right = buildTree(queue); // 递归构建右子树 return node; } } ``` ### 为什么用队列? 序列化后的字符串是按前序顺序排列的。反序列化时,我们按顺序一个一个取出来,每取一个就消耗一个。队列的 FIFO 特性正好满足这个需求。 ### 逐行拆解 ``` 序列化: 空节点 → 返回 "#" 非空节点 → "值,左子树序列化结果,右子树序列化结果" 反序列化: 从队列头部取一个值 如果是 "#" → 返回 null 否则 → 创建节点,递归构建左右子树 因为序列化和反序列化都是前序顺序,所以能正确还原 ``` ## 画图模拟反序列化 ``` 输入:"1,2,#,#,3,4,#,#,5,#,#" 队列:[1, 2, #, #, 3, 4, #, #, 5, #, #] 取 "1" → 创建节点 1 取 "2" → 创建节点 2(1 的左孩子) 取 "#" → 2 的左孩子 = null 取 "#" → 2 的右孩子 = null 取 "3" → 创建节点 3(1 的右孩子) 取 "4" → 创建节点 4(3 的左孩子) 取 "#" → null 取 "#" → null 取 "5" → 创建节点 5(3 的右孩子) 取 "#" → null 取 "#" → null 结果: 1 / \ 2 3 / \ 4 5 ✓ ``` ## BFS 版本 ```java // 序列化:层序遍历 public String serialize(TreeNode root) { if (root == null) return "#"; StringBuilder sb = new StringBuilder(); Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); while (!queue.isEmpty()) { TreeNode node = queue.poll(); if (node == null) { sb.append("#,"); } else { sb.append(node.val).append(","); queue.offer(node.left); queue.offer(node.right); } } return sb.toString(); } ``` ## 复杂度 - 时间:O(n) - 空间:O(n) ## 一句话总结 前序遍历 + 记录空节点(#),序列化和反序列化用同样的顺序,队列逐个消费就能还原。 --- 上一篇:[09 - 从前序与中序构造二叉树](./09-build-tree.md) | 下一篇:[11 - 路径总和 III](./11-path-sum-iii.md)
预览
发布文章
添加摘要让读者更快了解文章内容
取消
确认发布
AI 写作助手
输入一个主题,AI 将为你生成一篇 Markdown 博客文章
AI 正在写作中...
取消
开始生成
AI 优化助手
描述你的修改需求,AI 将在原文基础上进行补充或微调
AI 正在优化中...
取消
开始优化
画布
从已有图里选
✕
图名
保存后生成 /images/excalidraw/<图名>.svg(只能用字母、数字、短横线、下划线、点)
取消
保存并插入