刷 LeetCode 的树类题目第一道绕不过去的就是 94 题“二叉树的中序遍历”。这道题标记为“简单”但实际上一旦你顺着它往下挖会发现它几乎串起了二叉树最重要的几条主线递归的调用栈、迭代的手工栈、Morris 遍历的线索化思路以及前序中序后序三兄弟的统一框架。很多人做题就是把三种递归写法背一遍然后背一个迭代模板到面试时稍微追问一下“为什么 Morris 能做到 O(1) 空间”就卡住了。这篇内容不打算只讲 94 题本身的答案而是把中序遍历作为切入点把前序、中序、后序这三者怎么互相推导、怎么用同一套框架写出来、以及真正面试时最容易被追问的几个点一次性说清楚。适合刚入门二叉树、刷题刷到树这一章的同学也适合准备面试想把自己对遍历的理解再夯实一遍的人。1. 二叉树遍历的本质先搞懂“序”到底在说什么1.1 三种遍历的定义和记忆锚点二叉树遍历的“序”指的是根节点被访问的时机。这里要说清楚一个容易混淆的点不管是哪一种遍历每个节点的左子树和右子树的访问顺序是固定的永远先左后右变的只是根节点插在什么位置。前序遍历Preorder根 → 左 → 右。根第一个被访问。中序遍历Inorder左 → 根 → 右。根在中间被访问。后序遍历Postorder左 → 右 → 根。根最后被访问。很多教程喜欢用“根左右的顺序”来记忆但我个人更建议你换一个角度把每个节点都想象成一个小型的根然后递归地套用规则。比如中序遍历你在任何一棵子树上都是先完整处理左子树、再处理当前节点、再处理右子树。这样理解之后遇到复杂的嵌套树结构就不会晕。那中序遍历里“中”字到底指什么它指的是在整棵树上访问节点的顺序恰好是按照节点值从小到大的顺序前提是这棵树是一棵二叉搜索树BST。这一点是中序遍历面试含金量最高的性质因为大量题目考察的其实是这个隐含的递增序列。1.2 为什么中序遍历这么特殊前序和后序遍历也有自己的规律但中序有一个独一无二的特性对于 BST中序遍历结果是一个严格递增的序列。这意味着你可以用中序遍历去验证一棵树是不是 BST可以去第 k 小的节点甚至可以在遍历过程中做相邻节点值的比较比如 LeetCode 98 题验证二叉搜索树就是中序遍历的经典延伸。也正因为这个特性中序遍历是三种遍历里“应用面”最广的一个。刷题时如果题目涉及“排序”、“第 k 小”、“差值最小”之类的关键词大概率要用到中序遍历的思路。而后序遍历更多地用于树形 DP 和自底向上的归纳前序遍历则适合序列化和自顶向下的构建。我做了个表把三种遍历的常用场景整理出来方便你刷题时定位思路遍历方式访问顺序最典型应用场景前序根 → 左 → 右二叉树序列化、复制树、自顶向下 DFS中序左 → 根 → 右BST 的递增序列、验证 BST、第 k 小后序左 → 右 → 根删除树、自底向上计算、树形 DP2. 递归解法最简单的写法但你真的理解调用栈吗2.1 三行代码的中序遍历用递归写中序遍历核心代码只有三行反应了一个深度优先的过程。我先把完整代码贴出来用 Python 写C/Java 思路完全一致def inorderTraversal(root: Optional[TreeNode]) - List[int]: res [] def dfs(node): if node is None: return dfs(node.left) # 左 res.append(node.val) # 根 dfs(node.right) # 右 dfs(root) return res这个写法几乎不需要解释每个节点都严格按照“左根右”的顺序被访问。但递归的代码虽然简单它背后发生的事情一点都不简单你得弄清楚系统调用栈是怎么一层层压进去、再一层层弹出来的否则面试时容易被问倒。2.2 用一棵小树推演递归的执行过程假设我们有这样一棵简单的二叉树1 \ 2 / 3结构就是 root 11 的右孩子是 22 的左孩子是 3。中序遍历期望输出 [1, 3, 2]因为 3 在 2 的左子树里所以要先访问 3 再访问 2。用递归来走一遍调用 dfs(1)1 不为空先递归 dfs(1.left)。因为 1 的左子树为空这个调用立刻返回。然后访问根节点 1res 变成 [1]。再递归 dfs(1.right)进入 dfs(2)。在 dfs(2) 里先递归 dfs(2.left)这个节点就是 3于是进入 dfs(3)。dfs(3) 里先递归 dfs(3.left)空访问 3res 变成 [1, 3]再递归 dfs(3.right)空。此时返回到 dfs(2)访问根节点 2res 变成 [1, 3, 2]。最后处理 dfs(2.right)为空返回。这个过程中最关键的一点是当你在 dfs(2) 里调用 dfs(2.left) 时dfs(2) 的栈帧并没有消失它只是被暂时挂在栈里等子调用返回后再继续执行访问根节点的语句。这正是“递归就是隐式地使用调用栈”这句话的含义。在实际刷题时很多初学者总是在推演递归时卡住我觉得最好的方法不是硬在脑子里压栈而是直接打印调试信息或者在一张纸上把调用栈画出来。画法很简单每进入一个函数就在右边叠一个方块每返回一个函数就擦掉最上方的方块访问节点时记录序列很快就能把整个过程理顺。2.3 递归解法的复杂度与隐患递归解法的时间复杂度是 O(n)因为每个节点恰好被访问一次空间复杂度平均 O(log n)最坏 O(n)这取决于树的高度。这里的隐患值得专门拿出来说当二叉树退化成一条链时递归深度会达到 n此时调用栈会占用大量内存甚至导致栈溢出。在 LeetCode 上 n 通常不会大到让 Python 递归爆栈的程度但在真实工程的深度优先遍历里这必须作为一个风险点来评估。很多生产环境限制递归深度的原因就在这里不只是代码风格问题而是函数调用本身的栈开销是真实存在的。我们在第 3 节会看到迭代解法用显式栈模拟这个过程可以在同样的时间复杂度下把空间消耗控制得更可控同时避免递归爆栈的风险。3. 迭代解法显式栈模拟这才是面试要的重点3.1 为什么递归能做的事还要写迭代既然递归三行就能搞定为什么我们要学迭代面试官问这个问题想听的答案通常有两个层面一方面是性能层面递归用的是系统调用栈栈的深度受系统限制在树很深时可能会爆栈迭代用自己管理的数据结构来模拟空间可以更精确地控制。另一方面是理解层面把递归改写为迭代的过程本身就是在考察你能不能掌握“显式状态管理”的思路。这种能力在写非递归的树遍历、图的搜索、以及一些状态机相关代码时都很重要。再看一个实际的理由有些语言和平台对递归并不友好。嵌入式环境下栈空间非常有限递归很容易触发硬件层面的栈溢出而迭代解法只要用一个大小可控的数组或栈对象就能完成。你去看很多 C 语言实现的二叉树工具库都会刻意避开递归。3.2 迭代中序遍历的两种写法迭代中序遍历的经典思路是用栈保存“即将要处理的节点”一路向左走到底把路径上的节点压入栈然后依次弹出并处理再转向右子树。def inorderTraversal(root: Optional[TreeNode]) - List[int]: res [] stack [] cur root while cur is not None or stack: # 一路向左将路径上的节点全部压栈 while cur is not None: stack.append(cur) cur cur.left # 弹出栈顶访问它 cur stack.pop() res.append(cur.val) # 转向右子树下一轮循环处理它 cur cur.right return res外层循环里“当前节点存在或者栈非空”意味着还没有遍历完整棵树。内层 while 的职责是不断往左走把沿途节点入栈弹出节点时访问然后立刻切到右子树继续这个过程。另一种写法是更接近递归语义的“带状态入栈法”把每个节点的处理状态压入栈遇到未访问的节点就按“右、根、左”逆序压栈def inorderTraversal(root: Optional[TreeNode]) - List[int]: res [] stack [(root, False)] while stack: node, visited stack.pop() if node is None: continue if visited: res.append(node.val) else: # 中序是左根右压栈是逆序右、根、左 stack.append((node.right, False)) stack.append((node, True)) stack.append((node.left, False)) return res这个写法扩展性更强改前序和后序时只需要调整压栈顺序而且代码可读性也更好不容易搞混。3.3 边界条件和退出循环的辨析迭代解法最容易出 bug 的地方就是外层循环的条件。如果我写成while cur is not None当cur走到None但栈里还有节点时循环会提前终止导致右子树没被处理。反过来如果我写成while stack一开始空树时栈是空的cur是None也一样会出问题。所以正确条件是cur is not None or stack覆盖了“根节点为空”和“栈非空”两个阶段的场景。判断循环条件时一个实用的记忆方法是只要还有节点没被访问就说明要么手头有一个应该处理的节点cur要么栈里还有待处理的节点二者至少有一个成立。用这个逻辑去想就不会记错。空树的情况也要单独验证root为None时cur为Nonestack为空循环条件不成立直接返回空列表。这个简单的 case 是必须保证的否则后面所有解法都可能收到一个NoneType的错误干扰。3.4 时空复杂度的正确评估迭代解法的时间复杂度同样是 O(n)因为每个节点最多入栈一次、出栈一次。空间复杂度是 O(h)h 是树的高度因为栈中最多保留从根到一个叶子路径上的节点。在极端情况下链式树h n空间复杂度仍为 O(n)在平衡树中h log n空间复杂度则更优。这里有一个容易混淆的点递归解法的空间复杂度也包含树的高度如果算上系统调用栈迭代和递归两者的“大 O 表达”往往是一样的。真正的区别在于常数因子和“是否受系统栈限制”。只有 Morris 遍历才能突破这个限制把空间降到 O(1)我们下一节聊。4. 莫里斯遍历O(1) 空间的中序遍历线索二叉树的思想4.1 线索二叉树的核心理念Morris 遍历的空间复杂度是 O(1)它不借助额外栈而是巧妙地利用了树中大量空闲的 null 指针来记录回溯信息。这个思路和“线索二叉树”是一个道理本来节点的右指针如果为空就让它指向中序遍历下的后继节点左指针如果为空就让它指向中序前驱。通过这种方式Morris 能做到在遍历过程中不依赖栈也能知道“下一步该回到哪里去”。第一次接触时可能会觉得这像个魔术但其实逻辑非常朴素中序遍历时一个节点被访问完以后它的下一步应该是哪个节点一定是它的右子树的最左节点如果没有右子树就通过“线索”直接跳回到它的后继。树里空指针本来闲着也是闲着Morris 只是把这些空指针临时改造成了导航信息。4.2 用“贪心”的视角拆解执行流程Morris 中序遍历的每一步核心是在“建立线索”和“访问节点”之间做切换。算法的伪代码如下def inorderTraversal(root: Optional[TreeNode]) - List[int]: res [] cur root while cur is not None: if cur.left is None: # 没有左子树直接访问当前节点转向右子树 res.append(cur.val) cur cur.right else: # 找到左子树的最右节点中序前驱 predecessor cur.left while predecessor.right is not None and predecessor.right is not cur: predecessor predecessor.right if predecessor.right is None: # 建立线索让前驱的右指针指向当前节点 predecessor.right cur cur cur.left else: # 线索已存在说明左子树都处理完了访问当前节点断开线索 predecessor.right None res.append(cur.val) cur cur.right return res整个过程可以分成四条路来理解如果cur没有左孩那就意味着在当前子树里它已经是最左的节点了可以直接访问它然后进入右子树。如果有左孩就要先找到左子树里“最右下角”的节点这个节点是中序遍历里cur的前驱让前驱的右指针先指到cur。下次再通过这条线索回到cur时说明左子树已经处理完毕访问cur然后把线索断开恢复树结构再走右子树。4.3 一个生活化的类比系鞋带我第一次理解 Morris 时觉得最形象的说法是“系鞋带”。想象你在一个迷宫里探索走着走着发现可能要绕回来就提前做一个标记。Morris 就是这种思路要往左走之前先在你要回来的那个入口位置“系一根标记绳”这样等你转完左子树之后顺着标记绳就能直接回到该去的地方不需要把走过的路径都记录下来。在编码时建立线索就是在predecessor.right cur这一步相当于“系上绳子”当发现线索已经存在时predecessor.right is cur说明你已经通过绳子绕回来过一次这时候把绳子解开predecessor.right None再访问节点再往前走。每一步都没有多余的内存消耗所以空间是 O(1)。虽然 Morris 平时刷题用得少但在面试中讲出来会明显体现出你对“极致优化”的思考深度。而且它的思想在“线索二叉树”的考题里是直接相关的如果面试官问了“不用栈怎么遍历二叉树”这就是标准答案。4.4 莫里斯遍历的时间和空间复杂度分析Morris 遍历的时间复杂度看起来像是 O(n log n)因为找前驱时每个节点可能会被多次访问。但摊还分析后仍然是 O(n)每条边最多被走两次一次是建立线索一次是恢复线索时跳过。所以总执行次数还是线性的。空间复杂度是 O(1)但要注意这里指的是“除了输出数组之外的额外空间”。在实际刷题时res数组本身就是 O(n) 的所以你能省下的只是一个栈的空间。不少人在讨论时说“Morris 空间 O(1)”严格讲是“辅助空间 O(1)”用来存结果的数组不能算进去这个细节在面试中表述准确会加分。5. 前序与后序遍历三种遍历的统一框架5.1 前序遍历只要调整访问时机把 Morris 的思路改造成前序很简单。前序的顺序是“根左右”所以访问节点的时机比中序提前了当cur有左子树时在建立线索之前就访问cur而不是等线索绕回来之后才访问。如果用之前介绍的带状态入栈法前序只需要把压栈顺序改成逆序“右、左、根”。用普通迭代则可以改成def preorderTraversal(root: Optional[TreeNode]) - List[int]: res [] if root is None: return res stack [root] while stack: node stack.pop() res.append(node.val) # 栈是后进先出先压右后压左出栈就是先左后右 if node.right is not None: stack.append(node.right) if node.left is not None: stack.append(node.left) return res这个写法是很多教材里的标准模板理解起来比中序的迭代直观得多每次弹出栈顶访问然后把左右孩子按“先右后左”压栈下一轮先处理左孩子。5.2 后序遍历的经典技巧前序反转后序遍历写迭代稍微绕一点直接模拟“左右根”需要额外记录节点是否已经访问过。一个很聪明的技巧是前序遍历是“根左右”后序遍历是“左右根”如果把前序遍历改成“根右左”再把结果反转就得到“左右根”。这个技巧背后是数学上的对称性很多标准库的实现也会这么做。你可以利用前序风格的代码先访问根先压左再压右得到“根右左”的序列最后翻转def postorderTraversal(root: Optional[TreeNode]) - List[int]: res [] if root is None: return res stack [root] while stack: node stack.pop() res.append(node.val) # 注意这里压栈顺序与后序遍历统一框架的上一个写法相反 if node.left is not None: stack.append(node.left) if node.right is not None: stack.append(node.right) return res[::-1]这个方法的妙处在于你不需要额外维护状态只要修改压栈顺序并反转结果代码非常简洁。从工程角度来说反转一个数组是 O(n) 的整体时间复杂度依然是 O(n)在大部分场景下完全可接受。5.3 前序中序后序的统一迭代模板如果你不想背三套不同的迭代逻辑可以只背一个模板。这套模板的核心思想是给每个节点加一个“访问状态”未访问的节点按照“逆序”入栈访问过的节点再出栈时直接追加进结果。def preorderTraversal(root): res [] stack [(root, False)] while stack: node, visited stack.pop() if node is None: continue if visited: res.append(node.val) else: # 前序根左右 → 压入顺序为 右、左、根 stack.append((node.right, False)) stack.append((node.left, False)) stack.append((node, True)) return res中序只需要把最后的压栈顺序改成“右、根、左”后序改成“根、右、左”。很多人在考场上记不住多种模板用这个统一形式就可以在十几秒内推出任意一种遍历的迭代写法非常值得掌握。遍历入栈顺序从先到后访问时机前序右、左、根节点第一次出栈即访问中序右、根、左节点第二次出栈visited 为 True时访问后序根、右、左节点第二次出栈visited 为 True时访问5.4 从遍历序列反推二叉树这才是面试升级题有一个经典的出题方向知道前序中序或者后序中序能不能唯一确定一棵二叉树答案是可以。因为中序序列提供了左右子树的分界点前序或后序序列提供了根节点的位置两者结合就能逐步递归还原整棵树。比如前序序列的第一个元素一定是根在中序序列里找到这个根的位置左边的部分就是左子树的中序序列右边就是右子树的中序序列。再根据左右子树的长度把前序序列也切成对应的两段然后递归构建左右子树。这个思路在 LeetCode 105 题和 106 题里都有考察。但要记住一个限制只有前序中序或后序中序才能唯一确定一棵树前序后序在一般情况下不能唯一确定二叉树因为无法区分左右子树的边界。面试时如果被问到这个不要只答解法能把“为什么需要中序”这一点讲清楚才会让面试官觉得你真的懂了。6. 常见问题与排查实录6.1 递归深度过大怎么办在实践中如果二叉树是一个高度不平衡的退化链递归深度可能达到几万甚至几十万层在某些环境下会直接触发栈溢出。排查方法很简单如果代码在本地测试小数据时正常服务器上报栈溢出比如 Python 的 RecursionError那就基本可以确定是递归深度问题。解决思路有两个方向一个是用迭代解法重写这是最根本的另一个是如果必须保留递归结构可以考虑手动设置递归深度限制比如 Python 里的sys.setrecursionlimit(1000000)。但设置这个值是权宜之计它不是让递归变得安全而是暂时把崩溃的阈值提高真到了几十万层还是会爆。6.2 循环条件写错导致死循环或漏节点迭代解法里最容易犯的错误就是把while cur is not None or stack写成while cur is not None或while stack。前者会漏掉右子树的节点后者在树空时会直接退出结果倒是对了但很多正常场景会出错。排查这类问题时建议用最简单的三节点树根、左、右各一个做测试用例看输出是否合法。另一个容易出 bug 的细节是在 Morris 遍历里忘记断开线索。如果建立线索后没有在第二次碰到节点时把predecessor.right恢复为None那么后续遍历可能会成环导致死循环。这也是为什么 Morris 代码里predecessor.right None不能省掉的原因。6.3 序列为空时的返回值问题对于空树中序遍历应该返回空列表而不是返回None。很多实现里如果直接让res默认为None而不是空列表后面调用res.append就会出错。一个稳健的习惯是初始化res []并且在所有分支都只通过res.append和return res来返回。6.4 快速自测用例清单在实际提交 LeetCode 之前我会习惯性在本地过一遍这些自测用例几乎覆盖了所有边界空树root None期望输出[]单节点只有一个根节点期望输出[val]只有左子树或只有右子树的斜树完全二叉树比如[1,2,3,4,5,6,7]节点值可能为负数或 0不依赖值比较逻辑这几类用例能保证三种遍历实现的基本正确性也能帮你快速定位到是压栈顺序错了还是访问时机错了。7. 实操总结与后续扩展方向把 94 题做完之后千万别急着跳到下一题。我建议你做三件事第一把前序、中序、后序三种遍历的递归、迭代、Morris 三种写法都独立实现一遍。不要看模板而是自己从遍历定义出发推导代码。这个过程比刷十道题都有用因为你会真正理解“访问时机”和“压栈顺序”为什么是这样。第二找几道二叉树的中序应用题目来巩固。比如 LeetCode 98验证二叉搜索树、230BST 中第 K 小的元素、501BST 中出现次数最多的元素它们都是中序遍历的直接延伸。把中序遍历吃透这些题的解法会自然浮出水面。第三如果有余力想想这套遍历框架还能怎么用。比如在嵌入式领域一棵平衡的 AVL 树或者红黑树的遍历本质就是这三种遍历的工程化应用。再往深走数据库的 B 树索引也是基于“有序”遍历的思想你学到的排序性和遍历性知识在生产环境中其实是相通的。我个人在实际操作中的体会是中序遍历是所有树形结构题里性价比最高的一道题。它本身简单但它延展出去的方向几乎覆盖了树这一章节的全部核心考点。如果你能像我上面说的那样把递归调用栈、迭代显式栈、Morris 线索化这三条路线全部独立写一遍后续刷任何树的题目都会轻松很多。最后再分享一个小技巧遇到遍历题想不清楚时先在纸上画一棵三层的完全二叉树把访问顺序和一进一出的栈状态都写出来答案往往就自己浮现了。