想系统提升编程能力、查看更完整的学习路线欢迎访问 AI Compasshttps://github.com/tingaicompass/AI-Compass仓库持续更新刷题题解、Python 基础和 AI 实战内容适合想高效进阶的你。 第51课:序列化与反序列化模块:二叉树 |难度:Hard ⭐⭐LeetCode 链接:https://leetcode.cn/problems/serialize-and-deserialize-binary-tree/前置知识:第39课(二叉树中序遍历)、第44课(层序遍历)、第47课(前序中序构造树)预计学习时间:35分钟 题目描述设计一个算法,将二叉树序列化成字符串,并能将字符串反序列化恢复成原二叉树。你可以使用任何序列化方法,只要保证二叉树能被正确地序列化和反序列化即可。示例:输入:root [1,2,3,null,null,4,5] 1 / \ 2 3 / \ 4 5 序列化:1,2,null,null,3,4,null,null,5,null,null 反序列化:根据字符串重建上面的树约束条件:树中节点数在 [0, 10^4] 范围内-1000 Node.val 1000必须支持包含null的完整结构信息 边界用例(面试必考)用例类型输入序列化结果考察点空树rootnull“null”边界处理单节点root[1]“1,null,null”基本功能只有左子树root[1,2,null]“1,2,null,null,null”非完全树完全二叉树root[1,2,3,4,5,6,7]正常序列化标准情况包含负数root[-1,0,1]“-1,0,null,null,1,null,null”负数处理 思路引导生活化比喻想象你要把一个复杂的家族树打包快递到另一个城市,然后在那边完整还原。笨办法:拍照发过去——但照片无法表达空节点的位置信息,收到照片后无法确定树的确切结构。聪明办法:像读一本书一样按顺序报出每个位置的信息,包括这里是空的。比如:“根是1,左孩子是2,2的左孩子是空,2的右孩子是空,根的右孩子是3…”。这样对方就能完整还原整棵树了。关键洞察序列化的关键是保存结构信息,即每个节点的左右孩子位置,包括null;反序列化时按相同顺序读取即可还原。 解题思维链这一节模拟你在面试中从零开始思考的过程。Step 1:理解题目 → 锁定输入输出输入:二叉树的根节点 root输出:序列化:返回字符串(表示树的结构)反序列化:从字符串重建树,返回根节点限制:必须保存结构信息(包括null)序列化和反序列化必须是互逆操作Step 2:先想笨办法(层序遍历队列)用BFS层序遍历,把每个节点(包括null)都存入字符串,反序列化时也按层序还原。时间复杂度:O(n)问题:会产生大量的null占位符,字符串很长Step 3:瓶颈分析 → 优化方向笨办法的问题:层序遍历会在最后一层产生大量null字符串冗长优化思路:前序遍历:更紧凑,因为可以通过递归自然地处理null,不需要显式存储所有末尾的null递归设计:序列化和反序列化都用递归,代码简洁Step 4:选择武器选用:前序DFS序列化 递归反序列化理由:前序遍历(根→左→右)顺序清晰,容易理解递归写法简洁,代码量少相比层序遍历,前序遍历的字符串更短(不需要补全所有层的null)模式识别提示:当题目需要保存和恢复树结构时,考虑前序DFS递归或层序BFS队列 解法一:前序DFS序列化(递归法)思路按照前序遍历(根→左→右)的顺序,把每个节点的值(包括null)用逗号分隔存入字符串。反序列化时按相同顺序递归构建树。图解过程示例: 1 / \ 2 3 / \ 4 5 步骤1:前序遍历序列化 访问顺序:1 → 2 → 2的左(null) → 2的右(null) → 3 → 4 → 4的左(null) → ... 序列化字符串:1,2,null,null,3,4,null,null,5,null,null 解读: 1 ← 根节点1 2 ← 1的左孩子2 null ← 2的左孩子null null ← 2的右孩子null 3 ← 1的右孩子3 4 ← 3的左孩子4 null ← 4的左孩子null null ← 4的右孩子null 5 ← 3的右孩子5 null ← 5的左孩子null null ← 5的右孩子null 步骤2:反序列化(按相同前序顺序读取) 队列:[1,2,null,null,3,4,null,null,5,null,null] 递归构建: - 读1,创建根节点1 - 递归构建左子树:读2,创建节点2 - 递归构建2的左子树:读null,返回None - 递归构建2的右子树:读null,返回None - 递归构建右子树:读3,创建节点3 - 递归构建3的左子树:读4,创建节点4 - 读null,返回None - 读null,返回None - 递归构建3的右子树:读5,创建节点5 - 读null,返回None - 读null,返回None 最终还原出原树!Python代码fromtypingimportOptionalclassTreeNode:def__init__(self,val0,leftNone,rightNone):self.valval self.leftleft self.rightrightclassCodec: 解法一:前序DFS序列化 递归反序列化 思路:前序遍历保存节点值,null用占位符表示 defserialize(self,root:Optional[TreeNode])-str:将树序列化为字符串result[]defdfs(node):ifnotnode:result.append(null)# 空节点用null表示return# 前序遍历:根 → 左 → 右result.append(str(node.val))dfs(node.left)dfs(node.right)dfs(root)return,.join(result)# 用逗号连接defdeserialize(self,data:str)-Optional[TreeNode]:从字符串反序列化为树valuesiter(data.split(,))# 创建迭代器defbuild():valnext(values)# 按顺序取下一个值ifvalnull:returnNone# 前序遍历:根 → 左 → 右nodeTreeNode(int(val))node.leftbuild()# 递归构建左子树node.rightbuild()# 递归构建右子树returnnodereturnbuild()# ✅ 测试codecCodec()# 测试1:正常树root1TreeNode(1,TreeNode(2),TreeNode(3,TreeNode(4),TreeNode(5)))serialized1codec.serialize(root1)print(f序列化:{serialized1})# 1,2,null,null,3,4,null,null,5,null,nulldeserialized1codec.deserialize(serialized1)print(f反序列化验证:{codec.serialize(deserialized1)})# 应该与原字符串相同# 测试2:空树root2Noneserialized2codec.serialize(root2)print(f空树序列化:{serialized2})# null# 测试3:单节点root3TreeNode(1)serialized3codec.serialize(root3)print(f单节点序列化:{serialized3})# 1,null,null复杂度分析时间复杂度(n) — 序列化和反序列化都遍历每个节点一次具体地说:如果树有1000个节点,序列化需要1000次操作,反序列化也需要1000次空间复杂度:序列化:O(n) 用于存储结果字符串反序列化:O(h) 递归栈深度 O(n) 分割后的列表优缺点✅ 代码简洁,递归逻辑清晰✅ 前序遍历易于理解和实现✅ 字符串相对紧凑(比层序少很多null)❌ 需要理解递归和迭代器的配合 解法二:层序BFS序列化(队列法,最优解)优化思路用BFS层序遍历进行序列化,这样可以更直观地看到树的层次结构。虽然会产生一些额外的null,但逻辑更直观,且更容易扩展到其他应用场景(如树的可视化)。关键想法:层序遍历用队列实现,序列化和反序列化都用队列,逻辑对称,易于理解图解过程示例: 1 / \ 2 3 / \ 4 5 步骤1:层序遍历序列化 队列初始:[1] 输出:1 子节点入队:[2, 3] 队列:[2, 3] 输出:2, null, null (2的左右孩子) 子节点入队:无(都是null) 队列:[3] 输出:3 子节点入队:[4, 5] 队列:[4, 5] 输出:4, null, null (4的左右孩子) 队列:[5] 输出:5, null, null (5的左右孩子) 队列:空,结束 序列化字符串:1,2,3,null,null,4,5,null,null,null,null 步骤2:反序列化(按层序还原) 分割:[1,2,3,null,null,4,5,null,null,null,null] 索引:i0 i0:创建根节点1,队列[1] i1,2:节点1的左孩子2,右孩子3,队列[2,3] i3,4:节点2的左孩子null,右孩子null i5,6:节点3的左孩子4,右孩子5,队列[4,5] i7,8:节点4的左孩子null,右孩子null i9,10:节点5的左孩子null,右孩子null 完成!Python代码fromtypingimportOptionalfromcollectionsimportdequeclassTreeNode:def__init__(self,val0,leftNone,rightNone):self.valval self.leftleft self.rightrightclassCodec2: 解法二:层序BFS序列化(最优解) 思路:用队列进行层序遍历,逻辑直观 defserialize(self,root:Optional[TreeNode])-str:BFS层序遍历序列化ifnotroot:returnnullresult[]queuedeque([root])whilequeue:nodequeue.popleft()ifnode:result.append(str(node.val))queue.append(node.left)# 即使是None也要入队queue.append(node.right)else:result.append(null)return,.join(result)defdeserialize(self,data:str)-Optional[TreeNode]:BFS层序遍历反序列化ifdatanull:returnNonevaluesdata.split(,)rootTreeNode(int(values[0]))queuedeque([root])i1# 从第二个值开始whilequeue:nodequeue.popleft()# 处理左孩子ifilen(values)andvalues[i]!null:node.leftTreeNode(int(values[i]))queue.append(node.left)i1# 处理右孩子ifilen(values)andvalues[i]!null:node.rightTreeNode(int(values[i]))queue.append(node.right)i1returnroot# ✅ 测试codec2Codec2()# 测试1:正常树root1TreeNode(1,TreeNode(2),TreeNode(3,TreeNode(4),TreeNode(5)))serialized1codec2.serialize(root1)print(fBFS序列化:{serialized1})deserialized1codec2.deserialize(serialized1)print(fBFS反序列化验证:{codec2.serialize(deserialized1)})# 测试2:只有左子树root2TreeNode(1,TreeNode(2,TreeNode(3)))serialized2codec2.serialize(root2)print(f左子树序列化:{serialized2})复杂度分析时间复杂度(n) — BFS遍历每个节点一次空间复杂度:序列化:O(n) 队列和结果字符串反序列化:O(n) 队列和分割后的列表优缺点✅ 逻辑直观:按层序遍历,容易理解✅ 便于调试:可以直接看到每一层的节点✅ 易扩展:可以方便地改为打印层次结构✅ 面试推荐:队列操作标准,不易出错 Pythonic 写法利用Python的生成器和迭代器让代码更简洁:classCodecPythonic:Pythonic风格:使用生成器defserialize(self,root:Optional[TreeNode])-str:用生成器简化前序遍历defgen(node):ifnode:yieldstr(node.val)yieldfromgen(node.left)yieldfromgen(node.right)else:yieldnullreturn,.join(gen(root))defdeserialize(self,data:str)-Optional[TreeNode]:用迭代器自动移动指针defbuild(vals):valnext(vals)ifvalnull:returnNonenodeTreeNode(int(val))node.leftbuild(vals)node.rightbuild(vals)returnnodereturnbuild(iter(data.split(,)))解释:yield from可以优雅地递归生成值iter()创建迭代器,next()自动维护位置⚠️面试建议:先写标准版本展示思路,再提Pythonic写法展示语言功底。面试官更看重你的思考过程,而非代码行数。 解法对比维度解法一:前序DFS 解法二:层序BFS(最优)时间复杂度O(n)O(n)← 相同空间复杂度O(h)递归栈O(w)队列最大宽度字符串长度较短稍长(更多null)代码难度中等(递归迭代器)简单(纯队列操作)面试推荐⭐⭐⭐⭐⭐← 首选适用场景字符串紧凑性要求高通用,易理解和扩展为什么层序BFS是最优解:逻辑直观:按层遍历符合人的思维习惯,代码不易出错易于扩展:可以方便地改为打印层次结构、可视化树等面试友好:队列操作标准,面试官容易理解你的思路面试建议:优先讲解层序BFS方法(解法二),因为逻辑最清晰强调关键点:序列化:null节点也要入队,保证结构信息完整反序列化:用索引i依次读取左右孩子如果时间充裕,可以提及前序DFS方法作为优化(字符串更短)手动trace一个小例子,展示序列化→反序列化的完整过程 面试现场模拟面试中的完整对话流程,帮你练习边想边说。面试官:请设计二叉树的序列化和反序列化算法。你:(审题30秒)好的,这道题的核心是:序列化要保存结构信息,包括哪里是null反序列化要能按相同顺序还原树我的方案是用层序BFS:序列化:用队列层序遍历,每个节点(包括null)都存入字符串反序列化:用队列,按顺序读取值,依次连接左右孩子时间复杂度O(n),每个节点访问一次。面试官:很好,请写一下代码。你:(边写边说)fromcollectionsimportdequeclassCodec:defserialize(self,root):ifnotroot:returnnullresult[]queuedeque([root])whilequeue:nodequeue.popleft()ifnode:result.append(str(node.val))queue.append(node.left)# null也要入队queue.append(node.right)else:result.append(null)return,.join(result)defdeserialize(self,data):ifdatanull:returnNonevaluesdata.split(,)rootTreeNode(int(values[0]))queuedeque([root])i1whilequeue:nodequeue.popleft()# 左孩子ifvalues[i]!null:node.leftTreeNode(int(values[i]))queue.append(node.left)i1# 右孩子ifvalues[i]!null:node.rightTreeNode(int(values[i]))queue.append(node.right)i1returnroot关键点:序列化时,null节点也要加入队列,确保位置信息不丢失反序列化时,用索引i依次读取左右孩子的值面试官:测试一下?你:用示例[1,2,3,null,null,4,5]:序列化:“1,2,3,null,null,4,5,null,null,null,null”反序列化:i0:创建根1,队列[1]i1,2:1的左孩子2,右孩子3,队列[2,3]i3,4:2的左右孩子都是nulli5,6:3的左孩子4,右孩子5,队列[4,5]i7,8,9,10:4和5的左右孩子都是null还原成功!高频追问追问应答策略“为什么用层序而不是前序?”“层序更直观,按层处理符合思维习惯;前序也可以,字符串会更短,但递归逻辑稍复杂”“如果要求字符串尽可能短?”“可以用前序DFS,减少末尾的null;或者用后序遍历去掉尾部null,但反序列化会更复杂”“能不能用中序遍历?”“不能!中序无法唯一确定树的结构,比如[1,null,2]和[2,null,1]的中序都是[null,1,null,2],但结构不同”“空间能优化吗?”“序列化必须O(n)存储结果;反序列化的队列是必需的,无法优化,整体空间O(n)是最优的” 知识点总结Python技巧卡片 # 技巧1:用iter()和next()优雅地遍历valuesiter(data.split(,))valnext(values)# 自动移动到下一个,无需维护索引# 技巧2:deque的popleft()是O(1)fromcollectionsimportdeque queuedeque([1,2,3])queue.popleft()# O(1),比list.pop(0)的O(n)快# 技巧3:join连接字符串比高效result[]forvalinvalues:result.append(str(val))return,.join(result)# O(n),比逐个拼接的O(n²)快 底层原理(选读)为什么中序遍历不能用于序列化?反例:树1: 1 树2: 2 \ / 2 1 中序遍历:1,2 中序遍历:1,2 (相同!)两棵不同的树,中序遍历结果相同,无法区分。为什么前序和层序可以?前序遍历:[根,左,右],记录null后,可以唯一确定树:树1前序:1,null,2,null,null树2前序:2,1,null,null,null (不同!)层序遍历:按层记录,包括null,也能唯一确定。结论:序列化需要的是能唯一确定树结构的遍历方式,前序、后序、层序都可以,但中序不行。算法模式卡片 模式名称:树的序列化与反序列化适用条件:需要保存树的完整结构信息需要在不同系统间传输树数据需要持久化存储树识别关键词:“序列化”“持久化”“深拷贝树”“树的存储和恢复”模板代码:# 层序BFS模板fromcollectionsimportdequeclassCodec:defserialize(self,root):ifnotroot:returnnullresult,queue[],deque([root])whilequeue:nodequeue.popleft()ifnode:result.append(str(node.val))queue.extend([node.left,node.right])else:result.append(null)return,.join(result)defdeserialize(self,data):ifdatanull:returnNonevaluesdata.split(,)rootTreeNode(int(values[0]))queue,ideque([root]),1whilequeue:nodequeue.popleft()ifvalues[i]!null:node.leftTreeNode(int(values[i]))queue.append(node.left)i1ifvalues[i]!null:node.rightTreeNode(int(values[i]))queue.append(node.right)i1returnroot易错点 ⚠️序列化时忘记处理null错误:只存储非空节点的值问题:反序列化时无法确定树的结构正确:null节点也要用占位符(如null)表示反序列化时索引越界错误:忘记检查i len(values)问题:如果字符串格式不正确会导致IndexError正确:在访问values[i]前先判断if i len(values)用中序遍历序列化错误:以为任何遍历方式都可以问题:中序无法唯一确定树结构正确:只能用前序、后序或层序️ 工程实战(选读)这个算法思想在真实项目中的应用,让你知道学了有什么用。场景1:Redis持久化问题:Redis的数据结构(如Sorted Set底层的跳表)需要持久化到磁盘应用:用类似的序列化方法,将内存中的树状结构转换为字节流存储场景2:网络传输问题:微服务间需要传输复杂的层级数据(如组织架构树)应用:序列化为JSON字符串传输,接收方反序列化恢复场景3:深拷贝问题:需要完整复制一棵树,包括所有节点应用:序列化→反序列化,自动实现深拷贝️ 举一反三完成本课后,试试这些同类题目来巩固知识:题目难度相关知识点提示LeetCode 428. 序列化N叉树HardN叉树序列化用层序BFS,每个节点记录子节点数量LeetCode 449. 序列化BSTMediumBST序列化优化利用BST性质,可以省略null,用前序范围判断反序列化LeetCode 652. 寻找重复子树Medium树哈希用序列化的字符串作为树的哈希值,找重复LeetCode 331. 验证序列化Medium序列化验证不需要真的建树,用栈模拟验证格式LeetCode 1008. 前序遍历构造BSTMedium前序BST前序遍历范围约束反序列化BST 课后小测试试这道变体题,不要看答案,自己先想5分钟!题目:给定一棵二叉搜索树(BST),设计序列化和反序列化算法。由于BST有特殊性质(左根右),能否设计一个更紧凑的序列化方案(不需要存储null)?示例:输入:root [2,1,3] 2 / \ 1 3 你的序列化:2,1,3 (没有null!) 能否仅用这3个数字反序列化还原? 提示(实在想不出来再点开)BST的前序遍历是唯一的!利用BST的性质:在前序遍历中,对于每个节点,左子树的所有值都小于它,右子树的所有值都大于它。反序列化时用范围约束递归构建。✅ 参考答案classCodecBST:BST的紧凑序列化(无需null占位符)defserialize(self,root:TreeNode)-str:前序遍历,不需要存储nullresult[]defpreorder(node):ifnode:result.append(str(node.val))preorder(node.left)preorder(node.right)preorder(root)return,.join(result)defdeserialize(self,data:str)-TreeNode:用范围约束反序列化BSTifnotdata:returnNonevaluesiter(map(int,data.split(,)))defbuild(lower,upper):构建值在(lower, upper)范围内的子树valnext(values,None)ifvalisNoneorvallowerorvalupper:returnNonenodeTreeNode(val)node.leftbuild(lower,val)# 左子树值 valnode.rightbuild(val,upper)# 右子树值 valreturnnodereturnbuild(float(-inf),float(inf))# 测试codecCodecBST()rootTreeNode(2,TreeNode(1),TreeNode(3))serializedcodec.serialize(root)print(fBST序列化:{serialized})# 2,1,3 (只有3个数!)deserializedcodec.deserialize(serialized)print(f验证:{codec.serialize(deserialized)})# 2,1,3核心思路:BST的前序遍历 范围约束可以唯一确定树的结构,无需null占位符序列化:直接前序遍历,只记录值反序列化:用递归范围约束(lower, upper),如果当前值不在范围内,说明不属于这个子树,回退优势:字符串长度从O(2n-1)(包含null)减少到O(n)(纯值)如果这篇内容对你有帮助推荐收藏 AI Compasshttps://github.com/tingaicompass/AI-Compass更多系统化题解、编程基础和 AI 学习资料都在这里后续复习和拓展会更省时间。