LeetCode 94这道二叉树中序遍历是我在面试和带人刷题时反复提到的一道“入门即巅峰”的题目。题目描述只有两行给一个二叉树的根节点返回中序遍历序列。但就是这道题能把候选人的基本功、递归理解、栈的使用、甚至对二叉树结构的底层认知全部串起来。递归版本十行内写完迭代版本稍不留神就把入栈顺序写反Morris遍历更是很多工作五年以上的开发者也未必能在白板上一次讲清楚。这篇我按实战经验把四种主流实现从原理到代码再到坑点完整拆一遍供准备面试或想弄懂二叉树遍历本质的朋友参考。你可能会想中序遍历不就是左-根-右吗有什么好讲的其实不然。这个“左根右”的顺序在不同的实现方式下涉及的系统栈、显式栈、线索指针恢复完全是三套不同的思维模型。理解透了这三套模型你在 LeetCode 上后面遇到的 98、230、530 等 BST 相关题目都会顺手很多。我见过太多人递归秒写、迭代卡壳Morris 更是直接放弃这很可惜。因为面试官问这道题的目的往往不是看你能否 AC而是看你能在多大程度上解释“为什么能这样遍历”。1. 题目剖析与整体方案选型1.1 题目到底在问什么题目本身给的是一个二叉树节点结构每个节点有val、left、right三个字段。要求返回按“左子树-根节点-右子树”顺序访问的结果列表。二叉树遍历的核心说白了就是“访问每个节点的时机问题”而中序遍历的特殊性在于根节点的访问被夹在左右子树中间。这个夹在中间的顺序恰恰是二叉搜索树BST的灵魂因为 BST 的中序遍历结果是一个严格递增的有序序列这也是 LeetCode 98、230 等一堆题目的理论基础。举个最直观的例子1 / \ 2 3 / \ 4 5中序遍历结果是[4, 2, 5, 1, 3]。注意 2 在 4 和 5 之间1 在左子树整棵遍历完之后才出现。这个例子建议你在每一步实现时都拿来做“对拍验证”因为它的结构足够简单又能体现出三种形态有左子树、有右子树、叶子节点。1.2 为什么这道题值得做“一题多解”我先说结论这道题是二叉树题目中“复杂度梯度”最标准的一道。递归对应最简单的思维方式迭代展示如何用显式栈模拟系统栈Morris 则直接把空间复杂度压到 O(1)用线索指针实现空间换时间的极致优化。面试官在考察你时这四个字不是白说的——从易到难层层递进既能看基础也能看潜力。如果只写递归说明掌握基础但对栈的理解可能停留在“系统帮我做了”的层面如果能写迭代说明你理解调用栈的本质也具备控制状态的能力如果还能说清 Morris则说明你对二叉树结构本身有更深一层认知知道“空闲的右指针”可以被临时利用来省空间。这正好对应面试考察的“代码能力-机制理解-架构思维”三层递进。所以我的建议是不要只会递归就草草收工把这道题当成一个“样板工程”反复敲到三种方案都能独立手写。1.3 三种实现方案复杂度量化对比在动手写代码之前先用一张表把三个方案的核心差异看清楚之后所有细节都能在表里找到定位。实现方式时间复杂度空间复杂度核心思路面试推荐度递归O(n)O(h)最坏 O(n)函数调用栈天然支持回溯必会最先写显式栈迭代O(n)O(h)最坏 O(n)模拟系统栈的压栈/弹栈必会重点考查统一模板迭代null 标记O(n)O(h)用标记节点区分“访问”和“处理”扩展加分Morris 遍历O(n)均摊O(1)利用空闲右指针建立临时线索高级加分其中 h 是树的高度。这里要强调一点很多人误以为迭代的空间复杂度是 O(n) 因为“用了栈”实际上栈中同时存的最大节点数是树的高度并不是节点总数。只有链状树退化成链表时高度才等于 n。这个细节面试经常追问答错了很减分。1.4 影响范围不只是 LeetCode 94如果只把这道题当成一道“刷题”那确实有点亏。中序遍历的三种实现直接辐射到好几类问题BST 属性验证LeetCode 98中序序列必须严格递增本质就是验证中序遍历结果第 K 小元素LeetCode 230中序遍历计数到 K 即可提前返回BST 两节点最小绝对差LeetCode 530中序序列相邻差值取最小二叉搜索树与双向链表转换剑指 Offer 36用中序访问顺序重建双向链表二叉树的序列化与反序列化遍历顺序的选择会影响序列化结构。也就是说把这一题吃透后续很多题目你都自动拿到了“中序视角”。这也是为什么我逢人便推荐把 94 当作二叉树模块的“第一道精做题”。2. 递归实现最简单但绝不能轻视2.1 递归三要素的落地递归写起来像翻译定义先处理左子树再访问根再处理右子树。但很多人代码能跑通却说不清“递归为什么不会乱套”。我习惯把递归三要素对应到本题边界条件当前节点为空直接 return这是递归的“出口”否则会死循环函数逻辑对当前节点而言它的全部任务就是——递归处理 left、把自己的 val 加入结果、递归处理 right返回值设计这里可以用成员变量维护结果列表也可以传入引用/切片让每次递归不断追加。第三个要素值得多提一句。有些语言的函数式写法喜欢每次返回新列表这在算法面试中不是好习惯因为会引入额外的 O(n^2) 拼接开销。更好的做法是定义一个全局容器Python 里的self.res、C 里的引用参数、Java 里的成员 List递归时只负责往里面加。2.2 三种语言的递归代码对照先看 Python这段代码我在面试中写得最多也最推荐初学者模仿class Solution: def inorderTraversal(self, root: TreeNode) - List[int]: res [] def dfs(node): if not node: return dfs(node.left) res.append(node.val) dfs(node.right) dfs(root) return resC 版本注意引用传参class Solution { public: vectorint inorderTraversal(TreeNode* root) { vectorint res; dfs(root, res); return res; } private: void dfs(TreeNode* node, vectorint res) { if (!node) return; dfs(node-left, res); res.push_back(node-val); dfs(node-right, res); } };Java 版本用成员变量简化class Solution { private ListInteger res new ArrayList(); public ListInteger inorderTraversal(TreeNode root) { dfs(root); return res; } private void dfs(TreeNode node) { if (node null) return; dfs(node.left); res.add(node.val); dfs(node.right); } }三份代码的“骨架”完全一致区别只在语言的容器操作。我建议你至少把 Python 和 C 各写一遍因为前者面试常用后者对理解“栈帧”的概念更有帮助。2.3 复杂度推导为什么是 O(n) 时间和 O(h) 空间时间复杂度 O(n) 非常直观每个节点恰好被访问一次做一次常数时间操作。空间复杂度则需要解释清楚递归的空间来自系统调用栈每深入一层系统就把当前函数的局部变量、返回地址压入栈中。二叉树遍历的最大递归深度等于树的高度 h。这里给一个容易记的类比递归调用好比你在一个没有楼梯标记的商场里一层层下楼每走一层你就在本子上记一句“我在几层”系统栈就是那个本子。树越矮本子越薄树退化成一条链本子就和楼层一样厚了。平衡二叉树h log₂(n)空间 O(log n)链状二叉树h n空间 O(n)。这就是为什么递归实现“在极端输入下可能栈溢出”的原因。生产环境处理特别深的树时迭代实现往往是更保险的选择。2.4 递归题的“隐藏考点”能否被尾递归优化面试中经常有追问递归版本能不能改成尾递归这个问题很容易暴露对语言机制的理解。中序遍历不能写成尾递归因为第一次递归调用处理左子树之后还有“访问根节点”这个操作要做访问根之后还有第二次递归调用处理右子树。真正的尾递归要求递归调用是函数体最后一步操作没有任何后续逻辑。而中序遍历的递归调用天然夹着对根的访问所以无法直接尾递归优化。你能做的只是把结构改写成迭代用显式栈“手动实现”系统调用栈的效果。3. 显式栈迭代模拟系统调用的核心功夫3.1 为什么要用显式栈前面提到递归的栈溢出风险这是实际工程里的真实问题。另外面试官让你写迭代版本核心是想看你是否理解递归背后的“压栈-弹栈-恢复现场”机制。显式栈本质上就是把系统替你做的那件事自己再做一遍只不过你能够更精确地控制入栈顺序和访问时机。这里的关键认知是树的前序、中序、后序遍历在显式栈中的差异主要体现在“节点出栈时是否立即访问”和“子节点入栈的顺序”上。中序遍历的难点在于访问根节点的时机必须等左子树彻底处理完毕。3.2 核心策略先压左链弹栈访问再转向右子树我给的迭代模板是面试中最稳妥的一种思路拆成四步从当前节点出发一路向左把路上的每个节点都压入栈当 cur 为空时说明左边已经走到底了从栈里弹出栈顶节点并访问它把 cur 指向刚弹出节点的右孩子重复 1~3直到 cur 为空且栈也为空。为什么“弹出即访问”正好是中序因为第一步已经把左子树的所有节点按“先根后左右”的顺序压栈了但栈是后进先出所以左子树的节点会先被弹出。当弹到某个节点时说明它的左子树已经全部处理完毕此时访问根节点便恰好落在“左-根-右”的中间位置。来看一个模拟过程沿用前面的树1 / \ 2 3 / \ 4 5初始 cur 1一路压入 1、2、4直到 cur null栈为 [1, 2, 4]栈顶 4弹出 4 访问cur 指向 4.right null循环cur 为空弹出 2 访问cur 指向 2.right 5cur 5压入 5弹出访问 5cur 为空弹出 1 访问cur 指向 1.right 3压入 3弹出访问 3。最终顺序 [4, 2, 5, 1, 3]完全正确。每次“弹出访问”都意味着“该节点的左子树已经全部处理完”这句话就是迭代中序遍历的总纲。3.3 迭代代码Python、C、Java 三版Python 版本class Solution: def inorderTraversal(self, root: TreeNode) - List[int]: res [] stack [] cur root while cur or stack: while cur: stack.append(cur) cur cur.left cur stack.pop() res.append(cur.val) cur cur.right return resC 版本class Solution { public: vectorint inorderTraversal(TreeNode* root) { vectorint res; stackTreeNode* stk; TreeNode* cur root; while (cur || !stk.empty()) { while (cur) { stk.push(cur); cur cur-left; } cur stk.top(); stk.pop(); res.push_back(cur-val); cur cur-right; } return res; } };Java 版本class Solution { public ListInteger inorderTraversal(TreeNode root) { ListInteger res new ArrayList(); DequeTreeNode stack new ArrayDeque(); TreeNode cur root; while (cur ! null || !stack.isEmpty()) { while (cur ! null) { stack.push(cur); cur cur.left; } cur stack.pop(); res.add(cur.val); cur cur.right; } return res; } }几个实现细节Java 推荐用ArrayDeque而不是Stack因为Stack继承自Vector有同步开销而且ArrayDeque在栈操作上更高效外层循环条件cur || stack缺一不可。很多人写成while (cur)遇到根节点没有左子树的情况就漏掉了右子树内层while (cur)是关键它把“一路向左”的指针移动和“压栈”合并在一起写完记得检查指针是否越界cur.left可能为 null。3.4 面试追问这个迭代版背后是什么面试官大概率会问一句“你这个迭代版的空间复杂度是多少” 这时候别急着答 O(n)。准确说法是栈中同时存放的最大节点数为树的高度 h所以空间 O(h)最坏 O(n)。在平衡树上空间只有 O(log n)比递归版本的“直觉开销”少很多。再追问一层“能不能把空间再压一压” 这时候就可以引出 Morris 遍历了。面试官想听到的其实是“空间优化”这条链路递归 O(h) - 迭代栈 O(h) - Morris O(1)。如果你能主动把这条链路讲出来整个面试的观感会完全不一样。4. Morris 遍历用线索指针把空间压到 O(1)4.1 Morris 的核心思想利用空闲的右指针Morris 遍历是我个人觉得二叉树题目中最优雅、也最容易被忽视的一种实现。它不从“栈”的角度思考问题而是利用了二叉树中大量空闲的右指针。一个二叉树如果某个节点没有右孩子那它的right字段就是空闲的。Morris 的想法很朴素把这些空闲的右指针临时指向“在中序遍历中该节点的后继节点”这样就不需要栈来记录回溯路径了。这个思想在线索二叉树Threaded Binary Tree中有成熟的理论基础。区别只在于递归/迭代是“穿完再脱”Morris 则是“穿一下用一下用完就还原”整个过程不污染原始树结构。为了理解“后继节点”我多说一句。中序遍历中一个节点的“后继”就是遍历完它之后下一个要访问的节点。对于一个有左子树的节点它的“前驱”是左子树中最右侧的节点。Morris 找的正是这个“左子树最右节点”用它来作为临时线索的宿主。4.2 Morris 四步流程拆解当前节点记为 cur初始为 root。整个算法用四句话就能概括如果 cur 为空结束如果 cur 没有左子树直接访问 cur然后 cur cur.right如果 cur 有左子树找到左子树中最右的节点记为 predecessor如果 predecessor.right 为空说明还没建立线索则令 predecessor.right cur然后 cur cur.left如果 predecessor.right 不为空说明线索已经建过此时恢复现场predecessor.right null访问 cur然后 cur cur.right。这里第 4 步和第 5 步是很多人容易绕晕的地方。我提供一个记忆锚点每次遇到一个有左子树的节点Mark 一下它的前驱如果前驱没有右孩子挂上线索向左走如果前驱已经有右孩子了说明左边全部处理完访问当前节点再断开线索往前走。4.3 Morris 代码实现Python 为主class Solution: def inorderTraversal(self, root: TreeNode) - List[int]: res [] cur root while cur: if not cur.left: # 没有左子树直接访问当前节点 res.append(cur.val) cur cur.right else: # 找左子树的最右节点前驱 predecessor cur.left while predecessor.right and predecessor.right ! cur: predecessor predecessor.right if not predecessor.right: # 第一次访问到 cur建立线索继续向左 predecessor.right cur cur cur.left else: # 线索已存在说明左子树遍历完毕恢复现场后访问 cur predecessor.right None res.append(cur.val) cur cur.right return resC 版本代码结构几乎相同class Solution { public: vectorint inorderTraversal(TreeNode* root) { vectorint res; TreeNode* cur root; while (cur) { if (!cur-left) { res.push_back(cur-val); cur cur-right; } else { TreeNode* pre cur-left; while (pre-right pre-right ! cur) { pre pre-right; } if (!pre-right) { pre-right cur; cur cur-left; } else { pre-right nullptr; res.push_back(cur-val); cur cur-right; } } } return res; } };这里有一个非常关键的细节while (predecessor.right predecessor.right ! cur)中必须加上predecessor.right ! cur这个条件。否则在已经建立过线索的情况下又会把 pre 一路右移直接绕回 cur 本身导致死循环。4.4 为什么 Morris 的时间复杂度仍为 O(n)很多人的第一反应是这个算法不是要反复找前驱吗每个节点的前驱都要往右下走到最底那时间复杂度应该不止 O(n) 吧答案是每条边最多被访问常数次。具体来说对于每个节点找它的前驱时走的路径是“左子树的最右侧链”这条链上的节点在后续遍历中不会再次作为“前驱路径”走一遍。整体看下来整个遍历过程中每个节点最多被检查两次一次是建立线索时一次是发现线索已存在、断开恢复时。所以总复杂度是 O(2n) O(n)即均摊线性时间。空间复杂度是真正的 O(1)除了输入结果数组外只用了两个指针变量cur和predecessor。这也让 Morris 成为“原地遍历二叉树”的经典方案。4.5 Morris 在面试中的使用策略先说结论不会写 Morris 不影响你通过大多数面试但理解 Morris 能让你在“系统设计类追问”中多一个亮点。面试官通常先让你写递归再写迭代版如果你迭代版写得很顺他可能会试探性问一句“还有没有更省空间的方案”。这时候能把 Morris 讲得清楚至少说明你对二叉树结构有深一层的理解。如果你是面试准备期我更推荐“理解 手写”都做到但不建议一上来就背代码。先用手里的例子树把第 4.2 节的流程走一遍再对照代码看每一步对应哪个分支最后合上代码自己在白板上推一遍。我见过不少候选人把 Morris 背得很熟但画图时完全对不上号反而让面试官怀疑代码是抄的。5. 扩展思路其他实现方式与相关题目5.1 统一模板迭代用 null 标记区分访问状态前面讲到显式栈时中序和前序、后序的代码结构差别挺大。这里介绍一种“统一模板”用 null 作为标记把“已经处理过左右子树、可以访问的节点”和“还没处理、需要先处理子树的节点”区分开。思路是入栈时先按“右、根、左”的逆序入栈并在根节点入栈后再压入一个 null 作为哨兵。当弹出 null 时说明栈顶下一个节点已经处理完子树可以访问了。对中序遍历而言入栈顺序就是“右子节点、当前节点、左子节点”弹出时真正处理的顺序天然变成“左-根-右”。class Solution: def inorderTraversal(self, root: TreeNode) - List[int]: res [] stack [] if root: stack.append(root) while stack: node stack.pop() if node: if node.right: stack.append(node.right) stack.append(node) stack.append(None) # 标记当前节点的左右子树已入栈 if node.left: stack.append(node.left) else: res.append(stack.pop().val) return res这个模板最大的好处是前、中、后序只需要调整入栈顺序代码结构完全一致。想要前序就压“右、左、根 null”、后序就压“根、右、左 null”。在面试时如果你先写了这个统一模板也能展示出对遍历顺序和栈机制的系统理解。不过要注意这个模板比 3.3 节的经典迭代多压入了若干 null 标记空间上常数略高但仍是 O(h)。5.2 用“双栈/visited 标记”模拟递归还有一种思路是给每个节点记录“状态”来模拟递归——0 表示未处理、1 表示已处理。每次从栈里弹出节点如果状态为 1 就直接访问如果状态为 0 就把它和左右子树按逆序重新压入同时标记状态。这个方案的优点是语义清晰缺点同样是额外空间。其实这类方案本质上和统一模板一样都是“显式地维护每个节点的处理阶段”。面试里如果被问到“迭代与递归的区别”你可以顺手提一句“所有递归都能用栈模拟形态上就是用显式状态代替系统寄存器”。5.3 Python 生成器惰性求值的中序遍历在实际工程中有时我们并不想一次性把整棵树的遍历结果全部列出来而是希望“来一个处理一个”这时候可以用 Python 生成器实现惰性中序遍历。class Solution: def inorderTraversal(self, root: TreeNode) - List[int]: def gen(node): if not node: return yield from gen(node.left) yield node.val yield from gen(node.right) return list(gen(root))yield from会递归展开左子树、当前节点、右子树的迭代器。这种写法在“无限流”或“大规模数据分批处理”场景下很有用不过要注意递归生成器仍然受系统栈深度限制替代不了 Morris 的空间优势。5.4 由中序遍历延伸的高频变形题把 94 吃透以后下面这几道题基本等于“换皮不换核”LeetCode 98 验证二叉搜索树中序遍历得到序列判断是否严格递增LeetCode 230 二叉搜索树中第 K 小的元素中序计数到 K 就可以提前停止LeetCode 530 二叉搜索树的最小绝对差中序序列中相邻元素差值取最小LeetCode 501 二叉搜索树中的众数中序序列中相同值连续出现统计最多剑指 Offer 36 二叉搜索树与双向链表中序遍历过程中记录 pre 节点修改 left/right 指针构成链表。每道题做完我建议你都回头想一想能不能用 3.3 的迭代模板套能不能用 4.3 的 Morris 优化空间这样长期下来你就不是“刷了一道题”而是把一类解题范式内化成了自己的骨架。6. 常见问题排查与面试实战技巧6.1 高频报错与原因速查写中序遍历时的错误多数集中在这几类我按频率列出来错误现象可能原因定位与修复结果为空递归/迭代没处理根节点为空的情况或结果列表没传引用检查 base case确认结果容器在递归外创建结果顺序错乱迭代时入栈顺序写反把右子树当成左子树压栈记住“先压右、再压当前、最后压左、用 null 标记”的统一模板死循环Morris 查找前驱时 missingpredecessor.right ! cur补全 while 条件画图观察 pre 是否会绕回 cur栈溢出递归深度过大树退化成链表改用显式栈迭代或 Morris 压缩空间结果多出元素递归时对空节点也 append在 append 前增加空节点判断第 3 条是 Morris 最隐蔽的坑我当年第一次写时就是因为漏掉了predecessor.right ! cur导致死循环。排查方法也很简单打印 cur 的访问轨迹如果某一个 cur 值反复出现十有八九是线索没被正确断开。6.2 手写遍历的“对拍”技巧你在白板或纸上练习时强烈建议用一个固定的小树反复推演。我的习惯是固定用下面这棵树每次手推一遍三种方案6 / \ 2 8 / \ \ 1 4 9 / 3中序结果应该是[1, 2, 3, 4, 6, 8, 9]。推完以后再用这个结果去对照代码的每一步执行看看“哪个变量在哪个时刻指向哪个节点”。这个方法比盲目刷 10 道新题都管用因为中序遍历的递归和迭代执行过程能帮你建立“操作顺序”的直觉而这个直觉在应对其他遍历变体时是通用的。6.3 面试回答的三段式结构如果面试现场让你做这道题我建议按下面的节奏回答先说递归30 秒内写完讲述“左根右”的定义同时说明递归的时间和空间复杂度主动演进到迭代不用等面试官提示直接说“但递归用到系统栈极端情况下可能溢出所以我给你写一个显式栈版本”然后写 3.3 的代码解释“先压左链、弹出访问、转右子树”末尾提一句 Morris如果时间和面试官态度允许补充说“空间上最优可以做到 O(1) 的 Morris 遍历利用线索指针临时记录前驱原理我也可以简述”。这个流程最大的好处是既展示了基础扎实又体现出优化意识。最后一步即便不写完整代码能讲清楚 Morris 的“找前驱-建线索-恢复现场”三步通常就能给面试官留下很好的印象。6.4 刷题节奏与练习建议最后给个练习建议。第一遍刷题时一道题只求 AC 是不够的我建议你按“三遍法”来第一遍任意实现 AC重点理解题目意图和遍历顺序第二遍限时 15 分钟内写出递归 迭代两种版本并口头解释复杂度第三遍强制自己不看题解写出统一模板或 Morris并在白板上画出执行过程。三遍之后你对这题的理解基本就到了“肌肉记忆”程度。后续遇到 BST 相关问题先问自己一句“这题能不能用中序遍历解决”很多看似复杂的问题会瞬间简单很多。我个人在实际练习中的体会是Morris 遍历这一讲的价值远不止省那一点空间。它逼迫你从“栈/递归”的旧框架中跳出来真正去观察节点指针之间的拓扑关系。搞懂它之后再遇到“原地修改二叉树结构”这类操作你会比其他候选人从容得多。刷题不是目的把每种方案背后的“为什么”弄明白面试时才能做到举重若轻。最后再分享一个小技巧如果你时间有限至少把递归和迭代两种版本练到能够闭眼默写Morris 则做到“能讲、会画、代码看一遍能复现”这样在面试中已经足够支撑你在二叉树遍历类题目上站稳了。
