企业官网建设流程全解析

1. 题目定位：为什么“最简单”的遍历题能进hot100

力扣hot100第94题“二叉树的中序遍历”，因为写法过于基础，看起来像是给新手练手用的。但我刷了两轮hot100之后发现，这道题真正被高频收录的原因不在题目本身，而在它背后的三个层次：第一层是递归，第二层是显式栈模拟递归，第三层是Morris遍历的空间优化。几乎每一轮面试追问二叉树，都会从这里顺手往深处挖。

先看题目基本信息：给定一个二叉树的根节点root，返回它的中序遍历结果。所谓中序遍历，就是对于任意一棵子树，先访问左子树，再访问根节点，最后访问右子树。用生活里的例子理解，就像查一本书的目录——中序遍历得到的结果，恰好是把二叉搜索树展开成一个升序序列。这也是“二叉搜索树求第K小元素”这类题目的底层依赖。

这道题输入输出都不复杂：

• 输入：root = [1,null,2,3]
• 输出：[1,3,2]

一个空节点返回空列表，一个单节点返回它本身，边界极其简单。但如果你只是把递归写法背下来，会觉得这题毫无营养；如果你开始追问“递归的函数调用栈到底长什么样”“迭代写法为什么要用两个循环”“Morris遍历凭什么能O(1)空间”，这道题的含金量立刻就出来了。

我自己在实际刷题时，把这道题放在“二叉树遍历四件套”的第一题来对待。后面跟着的先序、后序、层序，基本都是从这份理解里派生出来的。可以说，中序遍历是理解整棵树的入口，同时也是面试官最喜欢借题发挥的起点。

2. 递归解法：三行代码背后的系统栈原理

2.1 递归代码与遍历顺序的对应关系

递归写法大概是不少人接触的第一版代码，Java实现如下：

class Solution { public List<Integer> inorderTraversal(TreeNode root) { List<Integer> res = new ArrayList<>(); inorder(root, res); return res; } private void inorder(TreeNode node, List<Integer> res) { if (node == null) { return; } inorder(node.left, res); res.add(node.val); inorder(node.right, res); } }

注意这里的执行顺序：先一路向左递归，遇到null才返回，回溯时再记录当前节点的值，最后进入右子树。代码里“记录res.add(node.val)”夹在两次递归调用中间，这一行代码的位置，决定了它是中序遍历。如果把这行放到第一次递归之前，就是先序遍历；放到第二次递归之后，就是后序遍历。

很多初学者会以为递归是整个函数执行完再返回，但实际上，递归函数是逐层压入系统调用栈执行的。每一层调用都会保存当前函数的局部变量和执行位置，当子问题返回后，系统会自动恢复上一层的执行现场，接着往下走。理解“执行位置恢复”这件事，是后面理解迭代写法的关键。

2.2 复杂度分析与递归的隐性成本

递归写法的时间复杂度是O(n)，每个节点恰好访问一次；空间复杂度是O(h)，h是树的高度。最理想的情况，树是平衡二叉树，h等于O(log n)；最坏情况，树退化成链表，h等于O(n)，递归深度会拉满，系统栈占用也随之拉满。

这里有一个实际工程里很常见的问题：当二叉树深度特别大，比如上万层的单链树，递归遍历会直接抛出StackOverflowError。力扣上普通测试用例基本不会触发这个错误，但真实业务里如果有一颗从数据库查出来的深层树结构，或者是一个设计不合理的层级关系表，递归遍历就可能在线上崩掉。这也是面试官追问“递归有什么缺点”时最常见的回应点。

我个人对递归的评价是：可读性满分，安全性随树高恶化。写业务代码时，如果无法保证树高可控，我通常会改用显式栈的迭代写法；如果连额外空间都想省掉，就上Morris遍历。接下来就把迭代写法的思路一步步拆开。

3. 迭代写法：自己模拟一套系统调用栈

3.1 为什么需要迭代写法

迭代写法去掉系统递归，本质上是自己用栈模拟系统的行为。系统递归栈帧里保存了两样东西：当前执行到哪一行、当前函数参数。我们自己维护的Stack里，也可以存节点和访问状态。但更漂亮、也是力扣官方题解使用的思路，并不需要在栈里存状态，而是利用“中序遍历天然先左后根”的结构，动态控制入栈和出栈时机。

中序遍历的过程可以概括成一句话：对于任意一个节点，优先处理它的左子树；左子树处理完了，才轮到这个节点自己；自己处理完，再去右子树。用栈实现时，具体操作是：

1. 从根节点出发，不停地把当前节点入栈，并走向左孩子，直到左孩子为空。
2. 出栈一个节点，这个节点就是“左子树处理完”的节点，此时记录它的值。
3. 把当前指针移动到它的右孩子，回到第1步，如果右孩子为空，就继续出栈下一个节点。

这个过程非常像在一个迷宫里沿着墙一路走，走到死胡同就退回上一个岔路口，再往另一个方向走。节点入栈的顺序，决定了回溯的路线。

3.2 迭代代码的两种实现方式

先看最常见、也最容易理解的版本，用两个循环完成：

class Solution { public List<Integer> inorderTraversal(TreeNode root) { List<Integer> res = new ArrayList<>(); Deque<TreeNode> stack = new LinkedList<>(); 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不为空，或者栈里还有节点。内层循环负责把当前节点及它的所有左孩子入栈。内层结束说明cur已经走到最左边的null处，此时栈顶就是“最左下角”的节点，也是本次中序遍历第一个要输出的节点。弹出它，记录值，再把cur指向它的右孩子，继续同样的流程。

另一种写法非常接近递归的语义，在栈里额外维护一个访问状态，用boolean标记节点是否已经处理过左右子树：

class Solution { public List<Integer> inorderTraversal(TreeNode root) { List<Integer> res = new ArrayList<>(); Deque<Object[]> stack = new LinkedList<>(); stack.push(new Object[]{root, false}); while (!stack.isEmpty()) { Object[] frame = stack.pop(); TreeNode node = (TreeNode) frame[0]; boolean visited = (boolean) frame[1]; if (node == null) { continue; } if (visited) { res.add(node.val); } else { stack.push(new Object[]{node.right, false}); stack.push(new Object[]{node, true}); stack.push(new Object[]{node.left, false}); } } return res; } }

这个版本的入栈顺序是“右、中、左”，因为栈是后进先出，所以实际取出顺序正好是“左、中、右”，完美复刻递归的调用顺序。它的优点是一套模板可以同时改写先序、中序、后序遍历，缺点是多存了一个状态位，占用的空间比双循环版本稍大，而且代码读起来更绕。

在实际面试中，我更推荐双循环版本。原因有两个：第一，它不依赖额外的状态标记，代码更精简；第二，面试官更容易通过“为什么内层循环一直在往左走”来考察你是否真正理解了中序遍历的本质。状态标记版本虽然通用，但容易给人“背模板”的印象。

4. 时空复杂度进阶：Morris遍历的低成本思路

4.1 Morris遍历到底在做什么

如果用递归或显式栈，空间复杂度最低只能做到O(h)。但如果允许临时改变树的结构，中序遍历可以做到O(1)额外空间，这就是Morris遍历。它利用的是叶子节点空闲的左右指针——尤其是右指针——来充当回溯线索。

Morris遍历的核心思想可以理解成“把没走过的路先标记好”。中序遍历要求访问完左子树之后必须回到根节点，但二叉树的节点没有指向父节点的指针，所以回溯只能靠栈。Morris的巧妙之处在于，在进入某个节点的左子树之前，先找到这个左子树在中序遍历顺序下的最后一个节点（也就是左子树中最右边的节点），把它的右指针临时指向当前根节点。这样当左子树遍历完，通过这个临时指针就能回到根节点，不需要额外存储。

这个“最右边的节点”在数据结构领域有一个专门的名字：前驱节点。中序遍历中，当前节点的前驱，就是左子树中最后一个被访问的节点。设置临时指针的过程，相当于给它加了一条“回头路”。

4.2 Morris遍历代码实现与关键判定

直接看Java实现：

class Solution { public List<Integer> inorderTraversal(TreeNode root) { List<Integer> res = new ArrayList<>(); TreeNode cur = root; TreeNode pre = null; while (cur != null) { if (cur.left == null) { res.add(cur.val); cur = cur.right; } else { pre = cur.left; while (pre.right != null && pre.right != cur) { pre = pre.right; } if (pre.right == null) { pre.right = cur; cur = cur.left; } else { pre.right = null; res.add(cur.val); cur = cur.right; } } } return res; } }

这段代码需要仔细理解的地方有两个。

第一，最内层的while寻找前驱节点，终止条件有两个：pre.right为空，说明是第一次来到这个位置，该设置临时线索；pre.right等于cur，说明之前已经设置过线索，这次是左子树遍历完成之后通过线索回来的。第二个条件是恢复原树结构的关键，也是很多初学者容易忽略的点。

第二，当节点左孩子为空时，直接访问当前节点并转向右孩子。这里的“右孩子”可能是真实的右孩子，也可能是之前某个前驱节点设置的临时线索。无论是哪种情况，路线都是正确的。

Morris遍历的时间复杂度从表面看不低，因为寻找前驱节点时可能多次沿右指针往下走，但整体摊还下来依然是O(n)。每个节点最多被访问两次：一次用于建立线索，一次用于通过线索回到父节点。实际跑起来比递归版本稍慢，但差距不大。树越扁平，Morris的优势空间就越小；树越高，省下的空间越可观。

我个人的建议是：笔试和面试手写代码优先递归或迭代，因为够用且不容易写错；Morris遍历可以当作加分项，面试官不问就不要主动抛，问了就把它讲清楚。它能体现对树结构底层指针的理解深度，是区分“背题选手”和“理解选手”的好题目。

5. 中序、先序、后序与线索二叉树的内在联系

5.1 三种深度优先遍历的排列规律

中序遍历不是单独存在的。先序、中序、后序三者本质上是同一个递归框架下，代码行的不同排列。很多热词里提到“二叉树的先序，中序，后序怎么确定”，其实就是考察这个排列逻辑。

• 先序：根、左、右。先处理自己，再处理左子树和右子树。
• 中序：左、根、右。先处理左子树，再到自己，最后右子树。
• 后序：左、右、根。左右子树都处理完，最后才到自己。

用栈统一处理时，如果采用状态标记法，只需要调整三个push的顺序就能切换遍历方式。比如中序入栈是“右、中、左”，先序入栈是“右、左、中”，后序入栈是“中、右、左”，取出顺序正好与入栈相反。

这里有一个很实用的记忆技巧：先序序列的第一个节点必然是整棵树的根；后序序列的最后一个节点必然是整棵树的根；中序序列中，根节点的左边是左子树的所有节点，右边是右子树的所有节点。根据这个特性，给定先序+中序，或中序+后序，就能唯一确定二叉树的结构。热词里“知道二叉树先序和中序 确定树的样子”说的就是这个问题。而先序+后序无法唯一确定树，因为无法区分左右子树的分界点。

我当时自己推导过一道经典题：先序序列是ABDECF，中序序列是DBEAFC，求原树。步骤很简单，从先序拿到根A，在中序中找到A，左边DBE是左子树，右边FC是右子树；回到先序，B是左子树根，C是右子树根；继续在中序里定位，就这样递归切割，很快就能画出整棵树。

5.2 线索二叉树与Morris遍历的关系

热词里单独出现了“线索二叉树”，这个知识点和中序遍历的关系非常深。普通的二叉树节点只有左右孩子指针，没有记录遍历顺序中前驱和后继的指针。线索二叉树的做法是：利用空指针域，把左空指针指向遍历序列中的前驱节点，右空指针指向后继节点，同时用布尔标记区分指针指向的是孩子还是线索。

Morris遍历实际上是“动态构建临时线索再删除”的过程，它不改变树的原始结构，遍历完又恢复原样。而传统线索二叉树是静态地把空指针变成线索，建好之后可以反复快速遍历。两者共享同一套思想基础：用额外的指针信息减少回溯成本。

如果你只是想AC题目，完全不需要碰线索二叉树；但如果你在准备面试时被问到“Morris遍历和前驱节点有什么关系”，能主动引出线索二叉树的概念，会显得知识体系很完整。这也是我把热词里“线索二叉树”这个概念放进这篇文章的原因。

6. 常见问题与避坑实录

6.1 力扣提交时最容易踩的坑

这道题的坑不在算法本身，而在实现细节上。第一个常见问题是返回值类型，题目要求返回List<Integer>，有人写成int[]，一提交就编译失败。力扣的模板已经给好了函数签名，老老实实用List即可。

第二个问题是集合初始化。不要用new ArrayList<>(null)这种方式，会抛NullPointerException。正确写法是new ArrayList<>()，然后在递归或迭代过程中add。

第三个问题就是递归版本的栈溢出。我见过不少人在本地跑得好好的，一放到力扣上遇到极端测试用例就爆栈。力扣对Java递归深度有一定的限制，虽然正常题目不会故意出退化成链表的大树，但如果你在真实场景里处理深层数据，栈溢出是必然的。迭代版本就没有这个担忧。

第四个问题容易被忽略：二叉树的节点值可能是负数，没有范围限制。有人会拿节点值当索引用，这显然不对，遍历顺序和节点值的大小没有关系。中序遍历输出的顺序只依赖树的结构，不依赖值的大小。

6.2 面试追问的高频变体

中序遍历这道题在面试里经常被改编成各种变体，我把常见的列在下面：

其中“验证二叉搜索树”和“第K小元素”是中序遍历最经典的两个应用场景。中序遍历二叉搜索树得到升序序列，这个性质几乎是所有相关题目的前提。比如LeetCode 230题，求二叉搜索树中第K小的元素，最直接的解法就是中序遍历，数到第K个节点。

我在面试中也被追问过“如何在不使用额外数组的情况下验证二叉搜索树”。思路是中序遍历时维护一个prev指针，每次当前节点值必须大于prev，否则就不是合法的二叉搜索树。这个做法空间是O(h)，依然只靠系统栈或显式栈，不需要额外存整个遍历序列。

6.3 关于遍历顺序的一个实用记忆方法

不少读者对先序、中序、后序的顺序感到混乱。我提供一个亲身验证过的记忆方法：想象自己在绕着二叉树画一圈轮廓。从根节点的左侧出发，沿着树的边缘走一圈再回到根节点。

• 第一次经过节点时记录，就是先序；
• 第二次经过节点时记录，就是中序；
• 第三次经过节点时记录，就是后序。

用这个思路理解中序遍历，节点会在从左子树上来的那个时刻被记录，正好对应“左子树处理完回到自己”的状态。这个视角比死记“左根右”要有用得多，因为遇到非递归写法时，你能判断出当前节点应该在第几次入栈时输出。

7. 从刷题到工程：中序遍历在真实项目里怎么用

很多人刷完力扣觉得这些数据结构题只存在于面试中，但实际上二叉树的遍历在工程领域应用相当广泛。我举几个真实场景。

第一个是处理层级化的组织架构或商品分类。后台系统经常把分类表设计成父子结构，从数据库查出来之后在内存里构造成一棵树。做全量导出时，中序遍历能按照“左子分类在前，父分类居中，右子分类在后”的规则输出一个结构化清单。虽然不是所有场景都需要中序，但如果树本身是一棵有序树，中序天然给出升序结果，非常有用。

第二个是表达式求值中的语法树解析。编译器把表达式解析成抽象语法树之后，中序遍历得到的序列恰好是去掉括号的中缀表达式。虽然实际编译器还要考虑运算符优先级，但中序遍历理解起来很直观。如果改成先序或后序，得到的是前缀表达式和后缀表达式，后者对于栈式计算机的求值特别友好。

第三个是JSON配置的路径查找。把嵌套配置解析成树结构之后，用中序遍历可以按顺序遍历所有叶子节点，方便做配置检查或自动补全。虽然一般更常用层序或递归深搜，但理解中序的思想能帮你更快地设计出合适的遍历策略。

我在实际写代码时，很少直接手写Morris遍历，因为业务代码更看重可读性。但理解它让我对“指针只是引用”这件事有了更深的认识，尤其在做资源释放或缓存回收时，能意识到临时修改结构必须及时复原，否则会产生难以排查的bug。

8. 刷题建议与个人体会

最后分享一点我自己的刷题经验。hot100里面的题，有些是高频面试题，有些是基础工具题，94题属于“工具题中的工具题”。它不直接决定你是否通过面试，但它是很多中等难度题目的解题前提。我建议把这道题当作一个锚点来刷：先掌握递归版本，再手写迭代版本，最后理解Morris遍历。三个版本对应三种对树的理解深度，也对应面试评分卡上的两档分数。

给初学者的建议是，千万不要觉得会写递归就跳过迭代。面试官最喜欢干的事，就是让你写个递归，然后追问“如果不允许用递归怎么办”。如果你只会递归，现场想迭代实现，很难一次写对，尤其是边界条件，很容易出现死循环或者漏节点。迭代版本的双循环结构，值得在纸上多画几遍。

给有经验的工程师的建议是，把这道题和二叉搜索树的性质绑定在一起复习。中序遍历二叉搜索树就是升序数组，这一个性质能串起至少十道hot100里的题目，比如验证二叉搜索树、第K大元素、二叉搜索树的最小绝对差、两数之和的BST版本等。每复习一道，就在纸上把中序遍历的框架写一遍，形成肌肉记忆。

我个人在实际操作中还有一个习惯：每道二叉树题都先想一想“如果这颗树退化成链表，我的方案会不会有问题”。这个习惯帮我避免了很多线上故障。如果你的代码在极端树形下还能稳定工作，那它的健壮性已经超过大多数工程实现了。

最后再分享一个小技巧：如果你在看题解时发现别人用了Deque而自己用的是Stack，建议一律换成Deque。Java官方文档已经不推荐使用Stack类，因为它在性能上和设计上都存在历史遗留问题。Deque的push和pop方法在语义上与栈一致，且底层效率更高。这个细节虽然对AC没有影响，但能让你在面试官面前显得更专业。