企业官网建设流程全解析

刷题刷到一定阶段，你会发现有些题非常“奇怪”：它被标成简单题，代码写起来也就十几行，但面试官偏偏爱拿它做追问的起点。LeetCode HOT 100的第94题“二叉树的中序遍历”就是这样一道题。表面上看，它只是三种遍历里最平凡的一种，可真正把它理解透了，你就能打通“递归和栈的关系”“树结构的基本遍历框架”“空间复杂度的边界判断”这几块最基础也最容易被问倒的内容。

这篇文章我不打算只贴一个标准答案。我会把这道题在面试里可能遇到的追问链条、三种写法的思路来源、复杂度里最容易说错的细节，以及我实际刷题和帮别人复盘时踩过的坑，一次性讲清楚。适合正在刷HOT 100的读者，也适合准备算法面试想把手写代码练扎实的同学。哪怕你目前只会背递归模板，读完也会知道迭代版到底在模拟什么。

1. 这道题为什么值得认真刷一遍

1.1 中序遍历到底在做什么——三行递归背后的树结构逻辑

很多读者第一次接触二叉树遍历，都会死记“左根右”三个字。中序遍历就是：先访问左子树的所有节点，再访问根节点，最后访问右子树的所有节点。这个定义看起来简单，但它隐含了一个重要的递归思想——对树中的每一个节点，访问顺序都要遵守同样的规则。

拿一棵最简单的手工树举例：根节点值是1，右孩子是2，2的左孩子是3。中序遍历要先看1的左子树，但1的左子树是空，所以1先被记录；接着进入右子树2，2有左子树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 List<Integer> inorderTraversal(TreeNode root) { List<Integer> res = new ArrayList<>(); inorder(root, res); return res; } private void inorder(TreeNode root, List<Integer> 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 List<Integer> inorderTraversal(TreeNode root) { List<Integer> res = new ArrayList<>(); Deque<TreeNode> 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 指向它的右子树，继续循环。

栈里装的，其实是“因为左子树还没处理完而被暂时搁置的祖先节点们”。每当访问完一个节点后，它的右子树会成为接下来的处理目标；如果右子树为空，程序会继续从栈里弹出上一个祖先。这个逻辑，就是系统递归调用时藏起来的调度逻辑。

我把递归版和迭代版做一个对照表格：

理解了这个对应关系，你就不需要在笔试时临时画栈图了。还有个细节很多人写错：弹栈之后一定要把cur指向pop出来的节点，而不是直接cur = cur.right。因为只有先拿到这个节点，才能记录它的值并确定它有没有右子树。res.add这一步放在弹栈之后，这是中序和前序迭代版的本质区别。前序遍历的访问时机是“压栈时”或“入栈前”，后序遍历的访问时机则要等到右子树处理完，中序刚好卡在中间。

2.3 Morris遍历：空间O(1)的线索化方案（选看/加分项）

如果面试官继续追问“你还能不能把空间复杂度压缩到O(1)”，那答案就是Morris遍历。这个解法不要求背，但值得理解——它代表了一种对树结构的深刻利用。

思路是利用叶子节点空闲的 right 指针（原本指向 null）来临时记录“访问完本节点后应该回到哪”。具体做法是：每个有左子树的节点 cur，都去找它左子树中最右的那个节点（也就是中序序列里 cur 的前驱），把前驱的 right 指针临时指向 cur。这样，当你顺着中序顺序访问完左子树的最右端，下一步就能通过这个临时指针回到 cur。

public List<Integer> inorderTraversal(TreeNode root) { List<Integer> 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 面试官的追问链条：从背题到真正理解

刷题到了一定程度，你会意识到面试的考察方式是递进的。同一个中序遍历，初级面试官只看你能不能写出来；资深的面试官会沿着一条追问链条往下走，每一步都在区分“背题选手”和“理解选手”。

我复盘了几次模拟面试，把典型追问链条整理如下：

1. “写一个二叉树中序遍历。”——这时你写递归版即可，10秒内完成。
2. “如果不用递归呢？”——你要切换到迭代版。重点不是代码对不对，而是你能不能讲清栈里保存的是什么。
3. “你这个迭代版的空间复杂度是多少？”——正确答案是O(h)。如果你回答O(n)，说明你把结果空间和栈空间混为一谈；如果你能主动解释h与n在链状树时的关系，这题就加分。
4. “能不能做到O(1)空间遍历？”——这就是Morris遍历的考点了。会写的人不算多，你能说出“用空闲right指针做线索”的核心思想，面试官基本满意。
5. “如果这棵树是BST呢？中序会得到什么？”——这里考察的是你对性质的理解和迁移能力。

整个问下来，没提前准备的人往往在第二问就开始支支吾吾。原因很简单：平时背的是代码，不是原理。所以如果你现在只会背递归版，我建议立刻补上迭代版的原理，不要等面试现场临时推导。

4.2 一个节点一个问题：如何定位自己的薄弱环节

我经常建议身边的同学用“自言自语法”自测中序遍历。所谓自言自语，就是不看代码，把思路用嘴说出来，说到你能让一个外行听懂为止。

• 如果你只能讲“左中右”三个字，说明你还没掌握递归的结构，需要回到函数定义本身去理解“做什么”而不只是“顺序是什么”。
• 如果你能讲清递归过程，但讲不清迭代版栈里面存的是祖先节点，说明你缺的是“系统栈转手工栈”的思维训练。
• 如果你会Morris但讲不清为什么前驱的 right 指针在第二次遍历时要恢复，说明你还停留在死记硬背步骤的层面。

这个方法非常管用。有一次我用它帮一位朋友复盘，他一口气写完了递归和迭代，还默写出了Morris代码，但当我问“第一次遇到前驱时为什么要设置right=cur”时，他停住了。这恰好暴露了他的真实弱点：他记住了所有分支条件，但没有理解“为了让遍历能走回根节点”这个根本目的。这种查漏补缺，比盲刷二十道题更有效。

4.3 关联题单：中序遍历后的扩展路径

吃透这道题之后，建议按下面这个顺序继续刷，每一题都会强化你的中序遍历框架：

这串题练下来，你对“树遍历”的理解会跨过一个门槛：遍历不再是机械地输出节点，而是变成一种可按需控制的执行过程。你可以中途停止、可以携带上下文状态、可以反向执行。这就是刷一道简单题收获的真正价值。

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三种写法连同复杂度都懂透，完全可以用这道题去检验自己是不是真的理解了二叉树遍历，而不是只记住了一个“左根右”。