1. 题目定位与核心思路拆解1.1 为什么“中序遍历”值得单独拿出来写LeetCode Hot 100 刷到第 27 题遇到的是一道“技术上不难但思想上非常关键”的题目——94. 二叉树的中序遍历。如果你正在准备面试这题几乎可以看作是二叉树系列的分水岭前面的反转二叉树、最大深度考的是递归思维的基础层到了中序遍历开始正式触及“二叉树和线性顺序之间的映射关系”。我之前带过不少同学刷题发现一个共性现象很多人能把中序遍历的递归写法背下来但一问到“为什么这个顺序是左-根-右”“迭代写法里为什么要用栈”“Morris 遍历到底在干嘛”就明显卡壳。这其实不是笨而是没有把这题的底层逻辑串起来。中序遍历不是一道孤立的题它是二叉搜索树升序输出、表达式树求值、线索二叉树构建、甚至后续很多“树转数组”问题的基础。把这一题吃透后面至少再遇到五六道 Hot 100 题都会顺畅很多。1.2 遍历顺序的语义和生活化理解中序遍历的定义非常简洁对一棵二叉树先遍历左子树再访问根节点最后遍历右子树。这个“左根右”的顺序在递归形态下几乎是一行代码的事但它不是凭空规定的而是为了满足一种实际需求——让节点按照“左小右大”的逻辑顺序输出。我习惯用一个生活化的类比想象你在整理一摞嵌套的文件夹。每个文件夹里分左夹和右夹中间夹着当前层的核心文件。中序遍历做的事情就是“永远先翻完左手边的所有子文件夹再取当前层的文件最后翻右手边”。这个顺序保证了在二叉搜索树里你拿到的永远是从小到大的有序序列。这一点在后面的 BST 验证、第 230 题二叉搜索树第 K 小元素中会反复用到。1.3 Hot 100 里这题的位置和出题逻辑题目编号是 94在 Hot 100 里排第 27 个按我刷题时的顺序。为什么 Hot 100 要把这题收进来因为它能同时考察三件事递归能不能写对、递归能不能改成迭代、迭代能不能优化到常数空间。这三个层次几乎覆盖了二叉树基础面试的全部考点。我在实际刷题中见过三种典型状态第一种只会递归迭代写不出来这类人容易被追问“递归转迭代”的变体题第二种迭代写出来了但空间复杂度是 O(n)距离最优解还差一档第三种能写出 Morris 遍历但说不清它和线索二叉树的关系。这篇文章想做的事情就是把这三档全铺开让你看完之后不管面试官从哪个角度切进来你都有话可接。2. 递归解法最优美的起点也是理解迭代的锚点2.1 递归解法的代码形态和调用栈真相先给出递归版本的实现这是最直接的解法class TreeNode: def __init__(self, val0, leftNone, rightNone): self.val val self.left left self.right right class Solution: def inorderTraversal(self, root: TreeNode) - list[int]: result [] self._dfs(root, result) return result def _dfs(self, node: TreeNode, result: list[int]) - None: if not node: return self._dfs(node.left, result) result.append(node.val) self._dfs(node.right, result)这个解法的时间复杂度是 O(n)因为每个节点恰好被访问一次。空间复杂度是 O(h)h 是树的高度——这里不是 O(n)很多人会记混。原因是递归调用栈的深度等于当前递归路径的长度而递归路径最长也就是从根到最远叶子节点的距离也就是树高。在最坏情况下树退化成链表h n此时空间才是 O(n)在平衡二叉树中h log n空间是 O(log n)。2.2 递归序的展开过程亲手走一遍才知道为什么我第一次真正理解递归遍历不是靠背代码而是靠手写“递归序展开”。拿一棵小树举例1 / \ 2 3 / \ 4 5对根节点 1 调用_dfs(1)不会立刻把 1 放入 result而是先进入_dfs(1.left)也就是节点 2。节点 2 又先进入_dfs(2.left)即节点 4。节点 4 的 left 为空直接返回然后把 4 加入 result。接着调用_dfs(4.right)为空返回。这样节点 4 的整个子树遍历完毕回到节点 2把 2 加入 result再去_dfs(2.right)——节点 5。节点 5 的 left 为空加入 5再访问 right 为空返回。节点 2 完成后回到节点 1加入 1最后_dfs(1.right)处理节点 3。最终的输出序列是[4, 2, 5, 1, 3]。注意观察节点 2 的输出顺序夹在 4 和 5 之间这正好体现了“左根右”的绝对优先级——无论左子树多深都得先把它彻底处理完。2.3 递归写法里的两个隐性坑递归写起来短但坑并不少。第一个坑忘记判空就访问node.val直接抛空指针异常。有人会说“我加了 if not node 啊”但在实际代码中很多人会在递归调用时写成_dfs(node.left, result)而不是_dfs(node.left, result)之前先判空——其实递归入口判空就够了关键是要保证每次访问 val 之前节点必然非空。第二个坑更隐蔽结果列表的传递方式。在 Python 里如果写成result.append(node.val)没问题但如果你尝试用result result [node.val]再传入下一层递归就会丢失之前累积的内容因为这是创建新列表而不是原地修改。这个坑在本地调试时数据量小看不出问题一旦树变深输出结果会变得非常诡异。3. 迭代解法用显式栈复刻系统调用栈3.1 为什么需要迭代写法面试官让你写迭代通常有四个潜在动机第一考察你是否理解递归的本质是函数调用栈第二考察你对栈这种数据结构在树遍历中的运用是否熟练第三防止你在递归深度过大时出现栈溢出虽然 LeetCode 上这题不会真的爆栈但生产环境中处理深度很大的树时这是实际问题第四为后续更复杂的 DFS 变体做铺垫。这里要强调一个关键认知迭代不是递归的替代品而是递归的底层实现。你在递归版本里使用的每一次函数调用系统都会在调用栈上压入一个栈帧保存当前的局部变量和返回地址。迭代版本要做的就是用自己创建的栈来模拟这个过程。3.2 核心模板左链入栈 访问 转向右子树迭代解法的标准代码如下class Solution: def inorderTraversal(self, root: TreeNode) - list[int]: result [] stack [] current root while current is not None or stack: # 一路向左把沿途节点全部压栈 while current is not None: stack.append(current) current current.left # 当前没有左子树可走了弹出栈顶并访问 current stack.pop() result.append(current.val) # 转向右子树继续同样的过程 current current.right return result这段代码的精髓在于两个 while 的配合。外层 while 的条件是current or stack意思是“只要还有节点没处理完就继续”。内层 while 负责深度优先地往左走把所有左孩子压栈。弹出栈顶后访问然后把 current 指向右孩子——如果右孩子为空下一次循环会继续弹出栈里剩下的节点如果右孩子非空则对右子树执行同样的左链压栈过程。3.3 手动模拟迭代过程一次透彻的走读还是用上面那棵树来走一遍初始current 1stack []result []。内层循环压入 1current 变为 2压入 2current 变为 4压入 4current 变为 None。弹出 4result [4]current 指向 4.right None。外层循环继续current 为 None 但 stack 不为空进入内层 while 时条件不满足current 为 None直接弹出 2result [4, 2]current 指向 2.right 5。对节点 5 执行内层循环压入 5current 变为 5.left None退出内层弹出 5result [4, 2, 5]current None。此时 stack 中还有节点 1弹出 1result [4, 2, 5, 1]current 3。对节点 3 执行内层循环压入 3current None弹出 3result [4, 2, 5, 1, 3]current Nonestack 为空结束。空间复杂度分析stack 里最多存的是“从根到当前节点的左链路径”最大长度等于树高 h所以空间是 O(h)。这里有个常见的错误说法是“迭代的空间复杂度是 O(n)”其实只有在最坏链状情况下 h n 才成立平衡树的迭代空间是 O(log n)。3.4 写迭代时的实战注意事项我在写这个模板时踩过两个坑。第一个是忘记把current current.right放在弹出节点之后立即执行。有些人会把这两步写反导致弹出节点后 current 还是那个节点于是死循环。第二个坑是把内层 while 的条件写成while current.left这样会漏掉当前节点本身——正确的做法是把 current 压栈之后再移动到 left所以判断的是 current 本身非空而不是 current.left 非空。如果面试官进一步追问“能不能不用栈”那就可以带出 Morris 遍历了。但要小心Morris 遍历改变树结构不同的人对“是否允许临时修改”有不同理解最好先说明“Morris 的思路是复用空闲指针”再展示代码。4. Morris 遍历常数空间的优雅解法4.1 为什么中序遍历能做到 O(1) 空间递归和迭代的空间开销都来自“记住路”的需要——递归靠系统调用栈迭代靠显式栈。Morris 遍历的核心思想是在遍历过程中临时改造树的结构用节点的空闲 right 指针记录回溯信息这样就不需要额外的栈空间了。哪些指针是“空闲”的对于中序遍历来说一个节点如果有左子树那么它在左子树遍历完之后需要回到自己。怎么回正常情况需要一个栈记录这个节点。Morris 的做法是找到当前节点左子树中最后被访问的那个节点也就是中序遍历中当前节点的前驱节点把它的 right 指针临时指向当前节点。这样当左子树遍历完沿着这个临时指针就能回到根节点。这个“前驱节点找法”其实和线索二叉树完全一致——Morris 遍历本质上就是在遍历过程中动态建立线索用完再恢复原状。4.2 Morris 遍历代码和两个阶段的状态流转class Solution: def inorderTraversal(self, root: TreeNode) - list[int]: result [] current root while current is not None: if current.left is None: # 没有左子树直接访问当前节点转向右子树 result.append(current.val) current current.right else: # 找到当前节点左子树的最右节点前驱 predecessor current.left while predecessor.right is not None and predecessor.right is not current: predecessor predecessor.right if predecessor.right is None: # 第一次访问当前节点建立线索 predecessor.right current current current.left else: # 第二次访问当前节点说明左子树已经遍历完 # 恢复树的原始结构访问当前节点转向右子树 predecessor.right None result.append(current.val) current current.right return result这段代码里最核心的判断是predecessor.right is not None and predecessor.right is not current。这个条件要表达的是前驱节点的 right 指针如果是空的说明当前节点是第一次遇到需要建立线索如果 right 指针已经指向了当前节点说明线索已经建好且左子树已经遍历完毕需要拆除线索、访问节点。4.3 Morris 遍历的复杂度真相和适用场景Morris 遍历的时间复杂度仍然是 O(n)这一点很多人会误判为 O(n log n)因为“找前驱”的过程看起来像是每次都要沿着左子树向下走一遍。但摊还分析可以证明每条边最多被访问常数次——建立线索时走一遍拆除线索时再走一遍所以总时间是 O(n)。空间复杂度是 O(1)因为只用了两个指针变量。Morris 遍历的代价是改变了树的临时结构。如果你在真实项目中遍历一棵树并且不允许任何副作用那 Morris 就不合适但如果是在 LeetCode 这类判题环境中题目不要求保持原树不变那 Morris 就是可行的。我个人在面试中通常先用迭代写法保证正确性如果面试官追问优化再展示 Morris同时明确说明“它的空间复杂度是 O(1)但会临时修改指针属于一种空间换约束的技巧”。4.4 Morris 理解的记忆锚点Morris 遍历初学者最容易搞混的是“什么时候访问节点”。记住一句话“左子树为空直接访问左子树非空第一次遇到不访问等第二次遇到才访问。”第一次遇到代表你在往下探索阶段第二次遇到代表你从左子树回来了这时候才是中序遍历中“根”的位置。这个记忆锚点比死记代码可靠得多。5. 二叉搜索树与中序遍历的强绑定5.1 中序遍历是 BST 的“升序输出函数”二叉搜索树的定义是左子树所有节点的值小于根节点右子树所有节点的值大于根节点。这个性质结合中序遍历的“左根右”顺序直接得到一个结论——对 BST 做中序遍历输出的序列必然是严格递增的。这个结论有多重要它几乎是“验证一棵树是不是 BST”的最快手段。在 Hot 100 里第 98 题“验证二叉搜索树”的一个经典解法就是中序遍历然后检查输出序列是否单调递增。第 230 题“二叉搜索树中第 K 小的元素”也是中序遍历到第 K 个节点直接返回。如果面试官出了这些问题本质上都是在考察 94 题的知识迁移。5.2 中序遍历序列的三种应用形态形态一全部遍历拿到完整有序序列。这个适合数据量小的场景比如把 BST 转成有序数组或者做树的序列化输出。形态二提前终止遍历到第 K 个就停。空间和时间都能优化适合 TopK、第 K 小这类问题配合迭代写法可以在找到答案后立即返回不需要遍历整棵树。形态三结合 Morris 做常数空间的第 K 小代码里加一个计数器遍历到第 K 个时记录答案并返回。这三种形态在实际刷题中都会出现。我的建议是先掌握递归写法应付“能过”的场景再掌握迭代写法应付“面试追问”最后掌握 Morris 应付“最优解”场景。三档都准备好这道题才算真正吃透。5.3 延伸从“左根右”到“右根左”的镜像思维理解了中序遍历实际上就理解了三种深度优先遍历的一半。前序遍历是“根左右”后序遍历是“左右根”它们和中序遍历的迭代代码高度相似只需要调整访问节点的时机即可。我在实际教学中总结过一个规律前序遍历是在压栈前访问中序遍历是弹出时访问后序遍历最麻烦需要额外记录“右子树是否已经访问过”。这里给一个额外的技巧后序遍历可以通过“中右左”的反向前序遍历再反转结果来实现也就是用中序遍历的迭代模板把“先左后右”改成“先右后左”然后反转结果列表。这条路在 LeetCode 上是可以跑的而且代码比标记法的后序迭代更短。6. 常见错误与排错技巧实录6.1 错误形态一空指针导致运行时崩溃这是初学者最高频的错误。表现在 LeetCode 上就是AttributeError: NoneType object has no attribute val。原因通常是递归函数里漏判了if not node或者在迭代内层循环结束后访问了已空的节点。排查方法很简单打印当前节点的值或者用assert node is not None在怀疑的地方加断言。我在本地调试时习惯用这段脚本def debug_traversal(root): result [] stack [] current root while current or stack: while current: print(fpush: {current.val}) stack.append(current) current current.left current stack.pop() print(fpop: {current.val}) result.append(current.val) current current.right return result把一棵小树输入进去观察 push 和 pop 的顺序很容易就能看出是访问时机错了还是指针移动错了。6.2 错误形态二中序遍历结果完全无序如果你跑出来的结果不是“左根右”顺序最常见的原因是把节点访问放在了左子树递归之前也就是写成了前序顺序。也有人会把current current.right误写成current stack.pop()导致节点反复被访问。这种情况建议回到递归版本先确保递归输出正确再对照迭代版本逐行检查逻辑。6.3 错误形态三Morris 遍历导致死循环Morris 遍历的死循环十有八九出在“拆线索”这一步。如果你建立了线索但忘记在第二次访问时把它置回 None那么下次循环走到同样位置时会再次把旧线索当作有效指针无限循环。最直接的排查方式是记录每个节点被访问的次数如果某个节点被“处理”了超过两次一定是线索没拆干净。还有一种情况是找前驱的 while 条件写成了while predecessor.right:没有加上and predecessor.right is not current这样遇到已经建立线索的节点会一直向右走到回头路。6.4 错误形态四递归深度过大导致栈溢出LeetCode 上 94 题一般不会触发这个问题因为默认测试数据树高有限。但如果你扩展去做一些深链树场景Python 默认递归深度是 1000 层遇到极端数据会抛RecursionError。这时候有两个选择一是用迭代写法规避递归深度限制二是用sys.setrecursionlimit()提高上限。我个人的习惯是如果预判树的高度可能达到几千层直接用迭代不用递归省得临时处理异常。6.5 实用调试技巧三步定位法第一步用小规模用例验证正确性。我固定使用[1, None, 2, 3]和[3, 9, 20, None, None, 15, 7]这两个用例前者测试“只有右子树的链状结构”后者测试“一般二叉树”。第二步在关键节点打印日志。递归版打印函数入参迭代版打印压栈和弹栈Morris 版打印“建立线索”“拆除线索”两个断点。第三步对照已知正确答案。不要用眼睛看树结构猜结果把树层序遍历展平成数组再用一个已验证的解法跑出标准答案多做几次对比。7. 题目变体与工程应用随想7.1 我在实际场景里看到的中序遍历中序遍历不是只在面试题里出现。我在参与过一个简单的规则引擎项目底层表达式树就是典型的“中缀表达式”结构——操作符在中间左右子节点是操作数或子表达式。求值时做的就是中序遍历只是从“收集节点值”变成了“根据节点类型执行计算”。另一个常见应用是数据库索引中的 B 树叶子节点本身是有序链表但这棵树的“逻辑语义”和人脑理解中的中序遍历非常相似——你需要按顺序扫描才能拿到有序结果集。如果你写过编译原理相关的代码“语法树的中序遍历生成中缀表达式”几乎是必做的事情。所以这题的价值不在题目本身而在于你通过它建立了一种思维模式树结构可以通过特定遍历序列和线性结构互相转换。7.2 从 94 题延伸出去的三条学习路径第一条路径二叉树的序列化与反序列化Hot 100 第 297 题。序列化的本质是找到一种遍历顺序让树可以唯一重建。前序遍历配合空节点标记是标准做法但中序遍历单独序列化不行因为中序序列不携带根节点位置信息。这个对比能帮你理解遍历顺序之间的本质差异。第二条路径迭代 DFS 的通用模板。你会发现前序中序后序的迭代写法都基于同一个“栈 指针”骨架只是访问时机不同。掌握了中序的迭代模板前序只需要把访问动作移到压栈前后序用“前序反转法”处理。第三条路径Morris 遍历升级版。Morris 前序和后序的代码看起来各不相同但核心都是“找前驱建线索拆线索”。如果你能把三种遍历的 Morris 写法都写出来二叉树基础就算彻底过关了。7.3 刷题策略上的建议我见过太多人把一个题刷完就急着做下一个结果一周后回来看代码完全想不起思路。对 94 这类“结构题”我的建议是当天把递归、迭代、Morris 三种写法各写一遍第二天只默写迭代版本第三天用 98 题和 230 题来检验自己是否真的理解了中序遍历。如果 98 题你能用中序遍历一次通过那说明 94 题的知识迁移已经完成了。另外一个建议不要只看题解要亲手画树、亲手模拟栈的变化。画图看起来慢但实际是加速理解的最快方式。我自己的习惯是在草稿纸上画一棵 7 个节点的树从递归到迭代到 Morris每层都手动走一遍之后再写代码就顺很多。8. 总结一点个人经验这题我前前后后刷过很多遍也带过不少人过这道题。最大的感受是中序遍历的三种写法不是三座孤岛它们是同一种思维在不同约束条件下的不同表现——递归用系统栈迭代用显式栈Morris 用树本身的空闲指针。你不需要一次性背下所有写法但要理解它们之间的演化关系。如果让我给一条最实际的建议那就是先用递归把“左根右”的语义刻进脑子里再用迭代模板解决“递归转迭代”的追问最后用 Morris 作为“你是否理解遍历本质”的加分项。三步走完这题就不再是刷题任务而是你二叉树功底的真正起点。