刷题刷到一定阶段你会发现有些题非常“奇怪”它被标成简单题代码写起来也就十几行但面试官偏偏爱拿它做追问的起点。LeetCode HOT 100的第94题“二叉树的中序遍历”就是这样一道题。表面上看它只是三种遍历里最平凡的一种可真正把它理解透了你就能打通“递归和栈的关系”“树结构的基本遍历框架”“空间复杂度的边界判断”这几块最基础也最容易被问倒的内容。这篇文章我不打算只贴一个标准答案。我会把这道题在面试里可能遇到的追问链条、三种写法的思路来源、复杂度里最容易说错的细节以及我实际刷题和帮别人复盘时踩过的坑一次性讲清楚。适合正在刷HOT 100的读者也适合准备算法面试想把手写代码练扎实的同学。哪怕你目前只会背递归模板读完也会知道迭代版到底在模拟什么。1. 这道题为什么值得认真刷一遍1.1 中序遍历到底在做什么——三行递归背后的树结构逻辑很多读者第一次接触二叉树遍历都会死记“左根右”三个字。中序遍历就是先访问左子树的所有节点再访问根节点最后访问右子树的所有节点。这个定义看起来简单但它隐含了一个重要的递归思想——对树中的每一个节点访问顺序都要遵守同样的规则。拿一棵最简单的手工树举例根节点值是1右孩子是22的左孩子是3。中序遍历要先看1的左子树但1的左子树是空所以1先被记录接着进入右子树22有左子树3所以先记3再记2。最终结果是[1,3,2]。注意这个结果不是按层来的也不是按数值大小来的它完全由“左-根-右”这个规则推导而来。如果这棵树是二叉搜索树中序遍历就会得到一个严格升序的序列。这是中序遍历最重要的一条性质很多题目——验证二叉搜索树、找第K小元素、把搜索树转成累加树——本质都在利用它。你可以把中序遍历理解为“把树压平到一条时间线上”每个节点在时间线上出现的位置取决于它左子树的规模。1.2 HOT 100里它的位置简单题是后续所有树题的地基HOT 100是很多人开启刷题计划时首先使用的题单它不按难度顺序排列而是按题目在面试中的出现频率精选出来的。第94题能被收录恰恰说明“树的遍历”本身就是一个被反复考察的基本功。不要因为它是简单题就觉得可以跳过——很多中等难度甚至困难难度的树结构问题都是在中序遍历框架之上做扩展的。我见过不少同学直接刷“验证二叉搜索树”时卡住卡住的原因不是那题复杂而是他们对中序遍历的理解停留在“能写出递归、记住顺序”的层面。一旦需要把遍历过程“停在某些条件上”或者“在遍历过程中比较相邻值”他们就不知道该怎么改了。这就是典型的地基不牢。把这道94题吃透后面遇到类似遍历类问题你至少知道代码从哪里下手。还有一个容易忽略的点这道题是练习“递归转迭代”非常好的载体。面试中有一类高频要求是“能不能不用递归实现”考的就是你能否用栈模拟函数调用。中序遍历的后序版本更难但中序恰好是一个承上启下的题目——它比前序多了一点弯绕又比后序简单是理解栈模拟的最好素材。2. 三种解法的核心思路拆解2.1 递归解法理解数学归纳法的“分而治之”递归版本是中序遍历最直观的写法代码量很小。先给出完整的类定义和最简实现public class TreeNode { int val; TreeNode left; TreeNode right; TreeNode() {} TreeNode(int val) { this.val val; } TreeNode(int val, TreeNode left, TreeNode right) { this.val val; this.left left; this.right right; } } public ListInteger inorderTraversal(TreeNode root) { ListInteger res new ArrayList(); inorder(root, res); return res; } private void inorder(TreeNode root, ListInteger res) { if (root null) { return; } inorder(root.left, res); res.add(root.val); inorder(root.right, res); }解读递归代码有个技巧不要试图在脑子里展开整个递归过程而是相信“函数定义”。inorder(root, res)的定义就是“把以root为根的树按中序顺序加入res”。那么要处理root这棵树就是先处理左子树再处理root本身最后处理右子树。这其实就是数学归纳法的思路基础情况是空节点不做任何事递归情况是假设左子树和右子树都能正确处理然后把三部分拼接起来。很多新手会问为什么递归里要传一个List能不能直接返回List当然可以但那样每次递归都要新建列表再合并代码更啰嗦也容易产生额外的内存开销。通过参数传递同一个res是刷题时更常见的风格也符合LeetCode测试驱动的习惯。递归版本虽然简单但有一个面试必考的知识点藏在里面递归调用会消耗系统调用栈。当树特别深比如每个节点只有右孩子递归的深度就是节点数n这时程序可能栈溢出。所以面试时写完递归面试官往往会追问一句“这个空间复杂度是多少”答案不是O(1)而是O(h)h是树高最坏情况下h等于n。2.2 迭代解法从系统栈到手工栈到底存了什么迭代版的中序遍历是所有“递归转迭代”问题里最值得背下原理、而不是背下模板的写法。核心思路是用显式的栈模拟系统调用栈。先上代码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; }这段代码很多同学背得滚瓜烂熟但被问“栈里存的是什么节点”就答不上来。这个问题太关键了。我来拆开讲外层循环的结束条件是cur null stack.isEmpty()。它表示当前没有待处理的节点同时栈里也没有等待恢复的祖先整棵树都遍历完了。内层 while 循环是不断往左走把路径上的节点压栈直到 cur 为空。此时栈顶元素就是整棵树上“最左且还未被访问”的节点。弹栈访问它因为它没有左子树了或者说左子树已经完全处理完现在轮到它本身。访问完之后把 cur 指向它的右子树继续循环。栈里装的其实是“因为左子树还没处理完而被暂时搁置的祖先节点们”。每当访问完一个节点后它的右子树会成为接下来的处理目标如果右子树为空程序会继续从栈里弹出上一个祖先。这个逻辑就是系统递归调用时藏起来的调度逻辑。我把递归版和迭代版做一个对照表格递归中的动作迭代版中的对应调用 inorder(root.left)压栈并进入左子树即cur cur.left递归最深开始返回弹栈即stack.pop()访问根节点值res.add(cur.val)调用 inorder(root.right)转向cur cur.right理解了这个对应关系你就不需要在笔试时临时画栈图了。还有个细节很多人写错弹栈之后一定要把cur指向pop出来的节点而不是直接cur cur.right。因为只有先拿到这个节点才能记录它的值并确定它有没有右子树。res.add这一步放在弹栈之后这是中序和前序迭代版的本质区别。前序遍历的访问时机是“压栈时”或“入栈前”后序遍历的访问时机则要等到右子树处理完中序刚好卡在中间。2.3 Morris遍历空间O(1)的线索化方案选看/加分项如果面试官继续追问“你还能不能把空间复杂度压缩到O(1)”那答案就是Morris遍历。这个解法不要求背但值得理解——它代表了一种对树结构的深刻利用。思路是利用叶子节点空闲的 right 指针原本指向 null来临时记录“访问完本节点后应该回到哪”。具体做法是每个有左子树的节点 cur都去找它左子树中最右的那个节点也就是中序序列里 cur 的前驱把前驱的 right 指针临时指向 cur。这样当你顺着中序顺序访问完左子树的最右端下一步就能通过这个临时指针回到 cur。public ListInteger inorderTraversal(TreeNode root) { ListInteger res new ArrayList(); TreeNode cur root; while (cur ! null) { if (cur.left null) { res.add(cur.val); cur cur.right; } else { TreeNode predecessor cur.left; while (predecessor.right ! null predecessor.right ! cur) { predecessor predecessor.right; } if (predecessor.right null) { predecessor.right cur; cur cur.left; } else { predecessor.right null; res.add(cur.val); cur cur.right; } } } return res; }这段代码对新手来说很容易绕晕关键要看懂predecessor.right ! cur这个判断。一个节点作为前驱被设置过临时指针后第二次访问到它时它的 right 已经等于 cur。这时候说明左子树全部处理完了所以要恢复原来的 null并且访问 cur再进入右子树。整个过程相当于把树临时织成了一张“线索网”遍历完又拆掉所以最终树的结构不会被破坏。Morris遍历的时间复杂度看起来像是O(n²)因为查找前驱的 while 循环会反复往上走。但摊还分析下来每个节点最多被额外经过两次——一次是挂线索一次是拆线索——所以总时间复杂度依然是O(n)。这个“看着像O(n²)其实摊还是O(n)”的说法本身就是面试中很加分的表述比直接背结论更能让人刮目相看。3. 复杂度与边界条件不踩坑的关键3.1 时间空间复杂度到底怎么算这道题的三种解法时间复杂度都是O(n)其中n是二叉树的节点总数。因为每个节点都会被访问一次没有任何节点被跳过或重复遍历Morris里虽然会重复经过某些路径但摊还下来仍是常数次。空间复杂度就很有讲究了递归版调用栈的深度等于树的高度h。平衡树时h约等于log n链状树时h等于n。所以最坏空间O(n)平均O(log n)。在分析时最好直接说“空间复杂度取决于树高最好O(log n)最坏O(n)”这样显得你理解边界而不是只背结论。迭代栈版和递归版本质一样空间复杂度同样是O(h)。虽然用的是手工栈但栈里装的节点数量依然取决于树高。注意不要把这里的栈和“遍历过程中所有节点的集合”混为一谈。栈只保存“当前路径上的祖先节点”不是整棵树。Morris版除了结果列表以外不需要额外栈所以是O(1)空间。这个“1”不随输入规模变化是真正的常数空间。还有一个坑很多人以为递归版的时间复杂度是O(log n)这是把递归深度和总节点数搞混了。访问所有节点的时间永远是O(n)递归深度只影响空间。3.2 空树、单节点、链状树三种边界测试写代码时顺手跑三个边界用例能挡掉大多数隐藏 bug。第一个是空树root为null时应该返回空列表。递归版第一行if (root null) return能直接处理迭代版外层循环条件cur ! null || !stack.isEmpty()初始时cur为null、栈为空直接跳过循环返回空列表。注意返回的是空列表而不是null——LeetCode通常会检查返回值返回null会导致判题失败。第二个是单节点树只有root一个节点。递归版会先调用inorder(root.left)发现是null直接返回然后把root值加入再调用右子树右子树也是null。迭代版会进入内层循环push之后cur变成null弹栈加入值然后cur指向null外层循环结束。这个用例主要是确认“根节点本身”能在正确时机被访问。第三个是链状树每个节点只有一个右孩子比如1-2-3。这是最容易出问题的场景之一。递归版虽然结果正确但如果树特别长会有栈溢出风险。迭代版由于栈中始终只保留当前节点路径也不会爆栈。最值得看的是Morris版每个节点都没有左子树所以会一路走cur cur.right走得非常顺畅也不会挂临时线索。3.3 中序遍历和BST升序性质一个隐藏的核心考点中序遍历对普通二叉树只是访问顺序对二叉搜索树却有特殊含义结果是递增序列。这条性质是整道题最值钱的副产品。面试中经常出现这样的变形给你一棵二叉树让你判断它是不是二叉搜索树。最直接的解法就是中序遍历一遍看结果是否是严格递增序列。代码上只需要在访问节点时维护一个 prev 变量比较当前值是否大于 prev。如果理解了这个性质你会进一步发现很多看似复杂的题目都可以化归为“中序遍历的变体”。比如“返回二叉搜索树中第K小的元素”本质就是中序遍历并计数比如“将二叉搜索树转为累加树”本质就是反向中序遍历先右后左累加访问过的值。所以第94题的关键不在“会写递归”而在你能否把它作为基础组件灵活迁移。4. 面试与刷题实战指南4.1 面试官的追问链条从背题到真正理解刷题到了一定程度你会意识到面试的考察方式是递进的。同一个中序遍历初级面试官只看你能不能写出来资深的面试官会沿着一条追问链条往下走每一步都在区分“背题选手”和“理解选手”。我复盘了几次模拟面试把典型追问链条整理如下“写一个二叉树中序遍历。”——这时你写递归版即可10秒内完成。“如果不用递归呢”——你要切换到迭代版。重点不是代码对不对而是你能不能讲清栈里保存的是什么。“你这个迭代版的空间复杂度是多少”——正确答案是O(h)。如果你回答O(n)说明你把结果空间和栈空间混为一谈如果你能主动解释h与n在链状树时的关系这题就加分。“能不能做到O(1)空间遍历”——这就是Morris遍历的考点了。会写的人不算多你能说出“用空闲right指针做线索”的核心思想面试官基本满意。“如果这棵树是BST呢中序会得到什么”——这里考察的是你对性质的理解和迁移能力。整个问下来没提前准备的人往往在第二问就开始支支吾吾。原因很简单平时背的是代码不是原理。所以如果你现在只会背递归版我建议立刻补上迭代版的原理不要等面试现场临时推导。4.2 一个节点一个问题如何定位自己的薄弱环节我经常建议身边的同学用“自言自语法”自测中序遍历。所谓自言自语就是不看代码把思路用嘴说出来说到你能让一个外行听懂为止。如果你只能讲“左中右”三个字说明你还没掌握递归的结构需要回到函数定义本身去理解“做什么”而不只是“顺序是什么”。如果你能讲清递归过程但讲不清迭代版栈里面存的是祖先节点说明你缺的是“系统栈转手工栈”的思维训练。如果你会Morris但讲不清为什么前驱的 right 指针在第二次遍历时要恢复说明你还停留在死记硬背步骤的层面。这个方法非常管用。有一次我用它帮一位朋友复盘他一口气写完了递归和迭代还默写出了Morris代码但当我问“第一次遇到前驱时为什么要设置rightcur”时他停住了。这恰好暴露了他的真实弱点他记住了所有分支条件但没有理解“为了让遍历能走回根节点”这个根本目的。这种查漏补缺比盲刷二十道题更有效。4.3 关联题单中序遍历后的扩展路径吃透这道题之后建议按下面这个顺序继续刷每一题都会强化你的中序遍历框架题目与中序遍历的关系98. 验证二叉搜索树中序遍历结果必须严格递增230. 二叉搜索树中第K小的元素中序遍历到第K个节点停止538 / 1038. 累加树反向中序遍历并累加99. 恢复二叉搜索树中序找逆序对然后交换105. 从前序与中序构造二叉树利用中序序列切分左右子树这串题练下来你对“树遍历”的理解会跨过一个门槛遍历不再是机械地输出节点而是变成一种可按需控制的执行过程。你可以中途停止、可以携带上下文状态、可以反向执行。这就是刷一道简单题收获的真正价值。5. 常见问题与避坑速查5.1 迭代模板死记硬背的隐患迭代版代码虽然短但我见过太多人栽在细节上。最常见的几个错误包括把res.add(cur.val)写在向左压栈的过程中导致中序输出变成了某种先序输出弹栈后忘记把cur指向刚弹出的节点而是直接指向cur.right导致第二次弹栈时访问了错误的节点外层循环条件少写cur ! null输入非空树时直接跳过循环返回空结果。这些错误有一个统一的排查方法画图模拟。随便画一棵三层树比如根1、左2、右3然后手动走一遍代码把每一步的 cur、栈顶、结果列表都写出来。走完一遍你就能发现到底是压栈时机不对还是弹栈后取值不对。画一次图比错三遍再查资料有效得多。还有一个隐藏问题是多数 LeetCode 题解不会提到的用Stack类还是Deque接口。Java 的Stack类由于历史原因默认性能较差新代码推荐用ArrayDeque来模拟栈。ArrayDeque 不支持 null 入栈但这里我们压的是 TreeNode不会是 null所以完全没问题。写代码时不要忽略这个细节面试手写时用 ArrayDeque 会显得你更懂工程实践。5.2 复杂度判断错误——“O(n)空间”错在哪里几乎每次讨论中序遍历都会有人把空间复杂度说成O(n)。这个错误出得很普遍因为它看起来太合理了遍历了n个节点总得要空间存吧关键是要分清两种空间存放结果列表的空间和算法本身额外使用的临时空间。LeetCode 的复杂度分析通常针对“除了返回值以外”的额外空间。所以递归版和迭代栈版的额外空间是栈的深度O(h)Morris版则是O(1)。同一道题从不同维度分析复杂度会有完全不同的答案。面试时主动把“结果空间”和“额外空间”区分开会显得你训练有素。如果把树高h和节点数n的关系理解成“n是上限h与节点分布形态有关”那么你就不仅能答对复杂度还能给出一个漂亮的补充说明平衡树中序遍历的空间复杂度是O(log n)退化为链表时是O(n)。这个补充是很多面试官喜欢的因为它展示了你对“树”这个结构的理解不是背定义而是看形态。5.3 刷题节奏与回顾技巧最后说点题外话关于怎么安排复习节奏。我的建议是“三次学习法”第一次接触看懂题解亲手敲一遍代码能跑通就算完成隔一天不查任何资料自己从头写一遍争取写出迭代版——这次的目标是独立推导即使写得慢也没关系再隔几天把递归版、迭代版、Morris版都拿出来每个都说出核心思路同时算对复杂度。第三遍时你会发现即使Morris版你没有完全背下来也能在纸上推演出来一个大概的框架因为原理已经懂了大半。这就达到目的了真正的掌握不是“断电默写”而是“给你十分钟想一想能自己推出来”。从这道题开始往后刷树的题目时建议你试着在每道题的笔记里记一行“本题和中序遍历的关系是什么”。哪怕这行字不写进任何文档也行只要你能在脑中过一遍。长期积累下来你的树结构刷题路线会非常成体系而不是一道一道孤立地记答案。我个人在实际刷题中的一个体会是把一道“简单题”吃透到能给别人讲清楚的程度比快速刷十道看完就忘的题有用得多。94题尤其适合做这种深度练习。如果你能把递归、迭代、Morris三种写法连同复杂度都懂透完全可以用这道题去检验自己是不是真的理解了二叉树遍历而不是只记住了一个“左根右”。