二叉树进阶必知：Morris遍历、序列化与树形DP实战解析-北京尧图网络

刷题刷到“16二叉树6”这个编号大概率你已经把二叉树的递归、层序遍历玩得比较熟了。但这个系列真正难的部分才刚刚开始Morris遍历怎么做到O(1)空间序列化字符串怎么避免歧义树的动态规划到底该返回什么这篇是二叉树专题的第六篇专门解决这些“从会写到写对”之间的问题。如果你正在准备算法面试或者刚开始系统刷树结构这篇文章可以当一份查漏补缺的清单用。我不会按教科书顺序把二叉树的定义再抄一遍而是直接从几个高频考点切入遍历的复杂度本质、Morris遍历、序列化与反序列化、树形DP、最近公共祖先。这些都是实战里最容易翻车又最能体现数据结构功底的内容。每一段我都会给出可运行的思路和代码再附上我自己踩过的坑。1. 先从递归遍历开始算账空间复杂度没你想的那么美1.1 递归调用栈的隐藏成本很多人学二叉树第一课就是递归前序遍历def preorder(root, res): if not root: return res.append(root.val) preorder(root.left, res) preorder(root.right, res)背下来容易但问一句“这个递归的空间复杂度是多少”不少初学者会答O(1)理由是只用了常数个变量。这是错的。递归不是“不需要额外空间”而是把每一层函数调用的现场都压进了系统栈。对于一棵高度为h的二叉树递归最深会同时存在h个栈帧每个栈帧里至少保存着参数root、返回地址、局部变量。所以空间复杂度是O(h)。在理想平衡树里h是O(log n)看起来很美。可一旦遇到一条链状的倾斜树h直接变成n空间复杂度退化为O(n)。很多线上内存超限的题不是算法不对而是递归深度在极端用例下把栈打爆了。所以凡是写到二叉树递归我建议先养成一个习惯在心里算一下树高。面试里经常追问“如果这棵树是一条链你的递归会不会爆栈”这不是刁难是在考察你知不知道递归的空间开销在哪里。1.2 用颜色标记法统一写出三种迭代遍历把递归改成迭代常见做法是用栈模拟但前序、中序、后序的迭代写法各不一样记起来很痛苦。我自己最常用的是一套“颜色标记法”思路是用一个二元组(node, visited)表示节点是否已经被处理过第一次遇到节点时visitedFalse把它和它的子节点按逆序压栈第二次遇到节点时visitedTrue直接输出值。以中序遍历为例def inorder_iter(root): res [] stack [(root, False)] while stack: node, visited stack.pop() if not node: continue if visited: res.append(node.val) else: # 栈是后进先出所以压栈顺序要反过来 stack.append((node.right, False)) stack.append((node, True)) stack.append((node.left, False)) return res这套写法的好处是前序、中序、后序只改压栈顺序逻辑高度统一不容易混淆。空间复杂度同样是O(h)但因为显式用栈你可以把栈放在堆上不受系统递归深度限制在某些编程语言里更可控。1.3 遍历顺序里藏着的“线索”线索如果你把中序遍历的迭代过程画出来会发现一个现象每个节点在被访问之前我们都要先从它的左子树一路扎到最左边这个过程大量时间花在“找下一个起点”上。有人就想能不能利用树里那些空闲的左右指针直接记录“下一个该访问谁”这其实就是Morris遍历的雏形也是下一节要展开的东西。所以遍历不只是背代码很多高级技巧都是从“遍历时浪费了什么”这个角度长出来的。2. Morris遍历不借用栈把树改造成“会自己走”的结构2.1 线索化的本质临时用right指针指向后继Morris遍历的核心思想是在遍历过程中把某些节点的右孩子指针临时指向它的中序后继这样就不需要栈来记录返回路径。访问完左子树后顺着这个临时线索就能回到父节点。等线索用完了再把指针恢复原样。举个例子对节点cur如果它存在左子树那么“左子树里最右边的节点”就是中序遍历时cur的前驱。这个前驱原本的right指针大概率是空的我们把它临时指向cur就形成了一条“走完左子树自动回到cur”的通道。这个思路不复杂但实现细节非常容易写错。尤其要注意不是所有节点的right指针都空闲所以需要两步判断——前驱right为空时建立线索前驱right已经指向当前节点时说明左子树访问完了要切断线索并访问当前节点。2.2 中序Morris遍历的完整拆解我先把中序Morris的代码贴出来再逐行解释为什么这么写。def inorder_morris(root): res [] cur root while cur: if not cur.left: # 没有左子树直接访问当前节点然后去右子树 res.append(cur.val) cur cur.right else: # 找左子树的最右节点中序前驱 prev cur.left while prev.right and prev.right is not cur: prev prev.right if not prev.right: # 第一次到达建立临时线索 prev.right cur cur cur.left else: # 第二次到达说明左子树已经访问完切断线索并访问当前节点 prev.right None res.append(cur.val) cur cur.right return res几个关键点建立线索后当前节点cur直接跳到cur.left把左子树当成一个“新的树”继续处理。第二次遇到同一个节点时前驱的right指针已经被我们改成了cur所以while prev.right and prev.right is not cur这个条件能把循环停住。切断线索的时机一定要在访问当前节点之前否则右子树遍历时会把旧线索当成真正的右孩子。2.3 前序Morris遍历的改写前序Morris和中序非常像差异只在访问节点的时机中序是在“第二次到达”时访问前序则是在“第一次到达”时访问。同样没有左子树时直接访问并向右走。def preorder_morris(root): res [] cur root while cur: if not cur.left: res.append(cur.val) cur cur.right else: prev cur.left while prev.right and prev.right is not cur: prev prev.right if not prev.right: prev.right cur res.append(cur.val) cur cur.left else: prev.right None cur cur.right return res后序Morris较复杂需要额外处理右子树的反转打印日常用得非常少面试也基本不会让你手写后序Morris所以我就不在这篇里展开了。2.4 Morris遍历的取舍面试值不值Morris遍历的时间复杂度摊还下来是O(n)空间复杂度仅为O(1)。这是它最迷人的地方也是它最“坑”的地方它通过修改树的结构来换取空间如果你的树后续还要用必须保证线索都被正确切断。连续写错两个分支就可能把原树改坏排查起来非常痛苦。我的建议是如果你的目标是快速通过面试优先掌握递归和迭代遍历Morris可以当作加分项。只有当面试官明确提到“空间复杂度能不能做到O(1)”时再上Morris。但既然已经写进二叉树系列第六篇说明它值得你至少看懂、能复现而不是只会背。3. 二叉树的序列化与反序列化树和字符串之间的往返3.1 为什么必须显式记录空节点序列化就是把二叉树变成一个字符串反序列化再还原成原树。最朴素的想法是只按某种遍历顺序输出节点值比如前序遍历输出1,2,3,4,5。但只靠前序你很难恢复结构因为不同的树可能产生相同的前序序列。比如根为1、左子树为2的树和只有左链1-2的树前序输出都是1,2如果省略空节点。解决办法就是补上空节点标记也就是所谓的“哨兵节点”。我用None或#表示空指针这样前序序列1,2,#,#,3,#,#就能唯一确定一棵树。从本质上讲序列化不是“把节点值拼起来”而是“把树的结构信息编码进去”。空节点标记就是结构信息的一部分丢了它反序列化就成了盲猜。3.2 前序序列化DFS 分隔符我常用的序列化方式是前序DFS用逗号分隔各个值空节点记为#。def serialize(root): def dfs(node): if not node: parts.append(#) return parts.append(str(node.val)) dfs(node.left) dfs(node.right) parts [] dfs(root) return ,.join(parts)为什么选前序而不是中序或后序因为前序DFS访问根节点最早反序列化时能立刻知道当前子树的根是谁递归结构最顺。中序序列化虽然也能做但你很难只凭中序序列重建二叉树至少要配合另一个遍历序列麻烦许多。这里有个细节节点值可能是负数、多位数所以一定要用分隔符。如果直接用空字符串拼接12和1,2无法区分负数还会和分隔符混淆。用逗号是最稳妥的。3.3 反序列化用一个索引指针重建反序列化是序列化的逆过程。我维护一个全局索引从左到右消费序列化列表def deserialize(data): vals data.split(,) def build(): nonlocal idx val vals[idx] idx 1 if val #: return None node TreeNode(int(val)) node.left build() node.right build() return node idx 0 return build()这段代码看着简单但有一个非常容易踩的坑反序列化时必须先创建根节点再递归创建左子树和右子树。顺序不能反也不能用for循环代替idx指针因为递归过程中不能依赖循环变量自动推进。另外Python里idx作为整数变量无法在嵌套函数里直接修改需要用nonlocal关键字或者用一个列表[0]包住。我一开始没用nonlocal直接报UnboundLocalError这个细节新手几乎都会遇到。3.4 反序列化的边界条件与常见错误序列化和反序列化的常见错误我归类成四种分隔符冲突节点值本身包含逗号不会发生但用其他特殊符号时要小心所以自定义分隔符时要选节点值里不可能出现的字符。空树处理序列化空树应该返回#反序列化#应该返回None。很多人只处理叶子不处理根为空导致空树用例直接崩。多余空格split(,)不会处理空格所以序列化时不要额外加空格否则反序列化时int( 1)会报错。递归深度如果树很高序列化和反序列化都用递归同样有爆栈风险。工程上需要改成显式栈但面试时通常可以先用递归讲清楚思路。序列化这个考点经常出现在“设计一个类”的题目里它考察的其实只有两件事有没有把空指针编码进去以及反序列化时能否不依赖额外信息地恢复结构。这两点想明白写代码只是体力活。4. 树形DP从“打家劫舍III”看递归返回值的正确姿势4.1 递归返回值不只是“结果”还可以是状态做过几道二叉树题目后你会发现很多问题的答案不是一个简单的return 值就能搞定的。比如经典的“二叉树打家劫舍”问题节点不能相邻同时选要求能偷到的最大金额。这时候如果只返回“当前子树的最大值”父节点无法判断子节点到底选了没选。所以正确的做法是让递归函数返回一个状态数组里面包含多种决策的结果再由父节点根据子节点的状态做组合。这就是树形DP的核心递归函数返回的不再是单一答案而是一个或一组状态值。父节点拿到子节点的状态后结合当前节点的约束条件算出自己的状态再向上传递。4.2 状态设计以“打家劫舍III”为例定义dfs(node)返回两个值not_rob不偷当前节点时子树能获得的最大金额rob偷当前节点时子树能获得的最大金额。如果偷当前节点那么左右子节点都不能偷所以rob node.val left_not_rob right_not_rob如果不偷当前节点左右子节点可以各自选择偷或不偷的较大值所以not_rob max(left_not_rob, left_rob) max(right_not_rob, right_rob)代码def rob(root): def dfs(node): if not node: return 0, 0 left_not_rob, left_rob dfs(node.left) right_not_rob, right_rob dfs(node.right) rob_cur node.val left_not_rob right_not_rob not_rob_cur max(left_not_rob, left_rob) max(right_not_rob, right_rob) return not_rob_cur, rob_cur return max(dfs(root))这里有几个容易错的地方空节点返回(0, 0)表示不管偷不偷收益都是0。结果取max(not_rob, rob)因为根节点可以选择偷或不偷。不要试图在递归里维护一个全局最大值这个问题的状态天然是向上聚合的全局变量反而容易混淆。4.3 二叉树直径与最大路径和同一个套路树形DP常见的还有两类题求直径任意两节点间最长距离以及最大路径和。它们的核心都是“经过当前节点的最优值如何由子树拼出来”。以二叉树直径为例def diameter_of_binary_tree(root): diameter 0 def height(node): nonlocal diameter if not node: return 0 left_h height(node.left) right_h height(node.right) diameter max(diameter, left_h right_h) return 1 max(left_h, right_h) height(root) return diameter这里height函数返回的是子树高度但在计算过程中顺便用left_h right_h去更新直径。这个写法有个特点递归函数的返回值服务于父节点但更新答案的动作发生在当前节点。这类题目背模板没用关键在于想清楚当前节点需要从子树拿到什么信息子树的这些信息如何组合成当前节点的答案当前节点向上传递的又是什么把这三个问题回答清楚树形DP的代码基本都是“后序遍历返回元组”的结构。4.4 树形DP的通用后序遍历模板树形DP虽然题目各不相同但骨架高度统一递归基处理空节点返回初始状态。后序遍历先递归左子和右子。在当前节点组合信息根据题目约束更新答案或状态。返回加工后的状态给父节点。我自己的习惯是先把第3步的状态定义写在注释里比如# return (包含当前节点的最大值不包含当前节点的最大值)。这样写一半不会忘记自己在干嘛。还有一个被忽略的细节树形DP的递归基不能一律返回0要结合状态定义。比如“最大路径和”中空节点的路径和应该是负无穷而不是0否则会把一条根本不存在的路径算进去。这是所有树形DP题里最容易出错的边界。5. 最近公共祖先LCA一棵树上最经典的路径查询5.1 后序遍历判定法递归返回节点或布尔值最近公共祖先问题面试出现频率极高。题目很直白一棵二叉树上给定两个节点p和q找它们的最低公共祖先。最直观的递归解法用后序遍历def lowest_common_ancestor(root, p, q): if not root or root is p or root is q: return root left lowest_common_ancestor(root.left, p, q) right lowest_common_ancestor(root.right, p, q) if left and right: return root return left if left else right理解这段代码的关键在于递归的返回值含义如果root为空返回None如果root是p或q直接返回root不需要再往下找如果左子树和右子树分别返回了非空节点说明p和q分居两侧当前节点就是最近的公共祖先如果只有一侧非空说明p和q都在那侧返回那一侧的结果。这个解法的时间复杂度是O(n)空间复杂度取决于递归深度。它虽然写起来只有几行但背后是“自底向上收集信息”的过程理解了它很多树的递归题都能迎刃而解。5.2 多次查询更优解倍增法思路如果在一棵树里要频繁查询多个点对的LCA单次递归O(n)就不够了。这时候常用倍增法。倍增法的思路是先把树预处理成一张“跳跃表”定义up[node][k]表示从node向上跳2^k步到达的祖先节点。预处理需要O(n log n)的时间和空间之后每次查询LCA只需要O(log n)。查询分两步把较深的节点向上跳到与另一个节点同一深度两个节点同时向上跳每次都尝试尽可能大的步幅找到最后一个不相等的祖先再上一级就是LCA。跳跃表有个特性与其说是“找到LCA”不如说是“找到LCA下面那层不重合的节点”。很多人第一次写容易跳过头所以往往需要先对齐深度再从大到小尝试步长。倍增法适合竞赛或高频查询场景在普通面试中手写一遍还是有点压力。我一般建议先把后序递归解法写熟如果面试官追问“查询很多次怎么办”再提倍增法思路不用现场把全部代码写完。5.3 其他LCA算法怎么选除了后序递归和倍增还有Tarjan离线算法、RMQ转LCA等。它们各有适用场景后序递归实现最简单适合单次查询倍增法适合多次在线查询代码量和理解成本中等Tarjan离线算法适合事先知道所有查询的场景复杂度为O(n q)但写起来复杂。日常刷题和面试能把前两者说清楚就足够优秀了。不要觉得算法越多越好能把一个思路讲透远比报菜名式的罗列更有说服力。6. 二叉树易错点自查清单与测试用例设计6.1 测试用例不能只用完美二叉树我见过很多同学刷二叉树题目测试用例永远是那棵1-2-3-4-5-6-7的完美二叉树结果代码交上去被边界用例打得头破血流。自己验证时至少要有这么几类用例空树None只有一个节点只有左子树或只有右子树的链状树左右子树高度差很大的非平衡树所有节点值相同的树节点值为负数、0、大整数的树。尤其链状树它能把“递归深度过大”的问题瞬间暴露出来。如果一道题要求迭代解你却写了递归解用一个10000层的左链马上就能测出来。6.2 递归边界返回值的四类陷阱树形递归最常见的边界错误我总结为四类空节点返回值选错有的是0有的是负无穷有的是(0,0)取决于状态定义。根节点特殊处理比如LCA问题里根节点是p或q时不能继续递归下去。全局变量初始值错误直径的全局最大值初始为0但最大路径和的初始值应该设为负无穷。子树缺失时的None处理递归左右子树时要先判断是否存在否则会出现None.left这种空指针错误。我发现把这四类问题记熟比刷二十道题更有用。因为边界错误永远是程序最隐蔽的bug来源。6.3 调试二叉树的实用小技巧二叉树问题调试起来比较麻烦我自己的经验是写一个简单的层序遍历打印函数把树的结构打印成数组形式[1,2,3,None,5]能直接看到树长什么样。对递归函数在入口处打印当前节点值和调用参数能快速定位哪一步返回值不符合预期。用“最小可复现用例”去测比如构造一个只有3个节点、p和q分别是两个叶子的小树然后手动推演一遍递归过程。这些技巧不需要花哨的工具但对排查逻辑错误非常有效。很多时候你盯着代码半天找不到问题打印几行出来立刻就能发现是left和right传反了。6.4 个人经验二叉树系列学到第六篇最该记住的三件事复盘整个二叉树专题我觉得有三件事最重要第一遍历是二叉树的基建。前序、中序、后序、层序不仅要会写递归还要能说清每种遍历顺序对应的实际应用场景比如中序在二叉搜索树里天然有序后序是树形DP的前提。第二递归函数设计三问返回值代表什么空节点返回什么当前节点和子节点怎么组合把这三个问题想明白再复杂的树形DP也不会无从下手。第三不要沉浸在“写出来就行”的错觉里。边界测试、复杂度分析、空间优化这三件事才是把一道二叉树题真正吃透的标志。我到现在写二叉树题目仍然会先在草稿纸上画一棵不对称的小树手动跑一遍递归再落到代码。这个习惯帮我省下了无数debug时间。如果你也想把二叉树这块彻底打通不妨从今天开始把每一道题都按这个方法过一遍。

二叉树进阶必知：Morris遍历、序列化与树形DP实战解析

相关推荐

Django小型超市管理系统实战：从ORM建模到部署排错的完整指南

短剧如何成为情绪急救箱？从即时反馈到心理代偿的治愈密码

全国机场吞吐量排名数据获取与清洗全攻略（2006-2024）

更多资讯

如何选择论文降重工具认准合规适配核心标准

大模型安全之四十五：从数据到输出----GenAI 版权、知识产权与伦理合规实战指南

梯度下降与反向传播算法：NYU-DLSP20 第二周课程笔记的数学原理与 PyTorch 实现

个人技能数据基础设施：构建可验证、可衰减、可进化的技能事件流系统

262K 长上下文实测：把整本书喂给 Yandex 新模型，它记住了多少

用JavaCC实现类C编译器：词法、语法、语义与三地址码全解析

今日更新

再见，SSE！你好，Streamable HTTP！轻松开发 Streamable HTTP MCP Server 并接入 TaoToken

工业软件标准化路线图：国产替代的落地施工图

VCMI安卓版实操指南：原生运行英雄无敌3的3步技术落地

本周精选

CMOS设计三大物理效应：体效应、沟道长度调制与亚阈值导电

微信小程序在线阅读毕设全解析：Java后端+MySQL+避坑实战

Android音频问题五层分析法：从App到Codec的系统化诊断

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？