二叉树中序遍历全解析：从递归到Morris遍历的进阶之路

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 ListInteger inorderTraversal(TreeNode root) { ListInteger res new ArrayList(); inorder(root, res); return res; } private void inorder(TreeNode node, ListInteger 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步如果右孩子为空就继续出栈下一个节点。这个过程非常像在一个迷宫里沿着墙一路走走到死胡同就退回上一个岔路口再往另一个方向走。节点入栈的顺序决定了回溯的路线。3.2 迭代代码的两种实现方式先看最常见、也最容易理解的版本用两个循环完成class Solution { public ListInteger inorderTraversal(TreeNode root) { ListInteger res new ArrayList(); DequeTreeNode 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 ListInteger inorderTraversal(TreeNode root) { ListInteger res new ArrayList(); DequeObject[] 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 ListInteger inorderTraversal(TreeNode root) { ListInteger 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 力扣提交时最容易踩的坑这道题的坑不在算法本身而在实现细节上。第一个常见问题是返回值类型题目要求返回ListInteger有人写成int[]一提交就编译失败。力扣的模板已经给好了函数签名老老实实用List即可。第二个问题是集合初始化。不要用new ArrayList(null)这种方式会抛NullPointerException。正确写法是new ArrayList()然后在递归或迭代过程中add。第三个问题就是递归版本的栈溢出。我见过不少人在本地跑得好好的一放到力扣上遇到极端测试用例就爆栈。力扣对Java递归深度有一定的限制虽然正常题目不会故意出退化成链表的大树但如果你在真实场景里处理深层数据栈溢出是必然的。迭代版本就没有这个担忧。第四个问题容易被忽略二叉树的节点值可能是负数没有范围限制。有人会拿节点值当索引用这显然不对遍历顺序和节点值的大小没有关系。中序遍历输出的顺序只依赖树的结构不依赖值的大小。6.2 面试追问的高频变体中序遍历这道题在面试里经常被改编成各种变体我把常见的列在下面变体核心思路复杂度验证二叉搜索树中序遍历结果必须是严格递增序列O(n)二叉搜索树第K小元素中序遍历计数第K个节点即答案O(K)求二叉树深度递归求左右子树最大深度加1O(n)二叉搜索树迭代器用栈维护下一个最小节点的访问路径均摊O(1)线索二叉树建树空指针指向前驱/后继供快速遍历O(n)其中“验证二叉搜索树”和“第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没有影响但能让你在面试官面前显得更专业。