作为常年面Java后端的人我对“二叉树的中序遍历”这道题感情很复杂。它看起来基础到不能再基础却几乎出现在每一轮技术面试里它最高频的解法写起来不到十行但面试官总能顺着这道题一路追问到递归栈溢出、迭代压栈、线索二叉树甚至Morris遍历。可以说吃透这一道题约等于把二叉树相关的基础和进阶考点都串了一遍。这篇文章就围绕“实现二叉树的中序遍历”展开我会把递归、迭代、Morris三种主流方案全部拆开讲透包括为什么这么写、过程中踩过哪些坑、面试官可能怎么连环追问尽量让不同基础的读者都能理解也能直接拿去用。适合看这篇文章的不光是正在备战面试的Java开发还包括刚开始学数据结构的在校生以及想系统梳理二叉树遍历体系的资深工程师。我会尽量用实际代码和经验心得来讲不整空洞的八股。1. 中序遍历是怎么一回事先搞懂“左根右”二叉树的遍历方式看着很多但本质上都是在回答同一个问题按什么顺序去访问树里的每一个节点。前序、中序、后序这三种深度优先遍历它们的差别只是访问根节点的时机不同。1.1 三种遍历顺序的区别前序遍历根左右先访问当前节点再递归左子树最后递归右子树。这种顺序适合复制树结构或者做序列化。中序遍历左根右先递归左子树再访问当前节点最后递归右子树。后序遍历左右根先递归左子树和右子树最后访问当前节点。适合做树的内存释放或者自底向上的归并操作。中序遍历有一个非常重要的特性在一棵二叉搜索树BST上做中序遍历结果是一个严格递增的有序序列。这一点让它成为了很多与排序、查找相关算法的基石。1.2 为什么中序遍历的输出顺序是确定的要理解中序遍历不能只背“左根右”得想清楚递归的过程。假设有一棵二叉树1 / \ 2 3 / \ 4 5中序遍历的过程是从根节点1出发先递归遍历左子树以2为根。在2的左子树中先访问4再访问2再访问5。回到根节点1访问1。最后递归遍历右子树以3为根访问3。所以输出顺序是4, 2, 5, 1, 3。这个过程里暗藏了一个关键点中序遍历的访问顺序是由树的结构唯一决定的和代码本身没什么关系。也就是说你可以在纸上画出任意一棵二叉树然后按照“先一路向左走到底访问再往回退访问父节点再转向右子树”的口诀手动推出中序序列。理解了这一点写代码就不会迷路。2. 最直观的递归实现三行代码背后的调用栈递归是解决树相关问题最容易上手的方式因为递归本身就天然贴合树这种递归结构。中序遍历的递归代码几乎可以直接照抄定义。2.1 递归代码与时间复杂度分析用Java实现中序遍历的递归版本如下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 result new ArrayList(); inorder(root, result); return result; } private void inorder(TreeNode node, ListInteger result) { if (node null) { return; } inorder(node.left, result); result.add(node.val); inorder(node.right, result); }这个解法的时间复杂度是O(n)因为每个节点恰好被访问一次。空间复杂度是O(h)h是树的高度也就是递归调用栈的最大深度。在极端情况下如果是一棵链状树每个节点只有左孩子或只有右孩子h等于n空间复杂度会退化为O(n)。2.2 递归写法在面试中的陷阱很多初学者觉得递归写法无所谓写出来就完事了。但面试官往往会在这一步设下第一个坎如果树的高度非常深比如10万层递归会怎样答案是栈溢出。JVM的调用栈深度有上限默认情况下几百到几千层深就可能抛出StackOverflowError。这也是为什么面试官通常会追问一句“你还能写出非递归版本吗”。在实际生产环境里如果面对的是不可控的输入数据递归遍历一颗深度很大的树是一件有风险的事情。所以迭代版本的写法不只是为了应付面试它本身就是工程中需要掌握的能力。另外一个容易被忽略的细节是递归时我单独抽了一个inorder辅助方法而不是在inorderTraversal里直接递归。这样做的目的是让对外暴露的方法签名保持干净同时避免了每次递归都新建ArrayList的性能损耗。很多初学者会写成下面这种低效版本public ListInteger inorderTraversal(TreeNode root) { ListInteger result new ArrayList(); if (root null) return result; result.addAll(inorderTraversal(root.left)); result.add(root.val); result.addAll(inorderTraversal(root.right)); return result; }这个写法在逻辑上完全正确但每次递归都会创建新的List还需要做集合合并时间复杂度和内存开销都会变大。在面对大规模数据时这种“看起来没问题”的写法可能会成为性能瓶颈也容易被有经验的面试官诟病。3. 迭代实现用显式栈模拟递归过程非递归中序遍历是面试的高频考点。它比递归多了一层思考需要手动维护一个栈来模拟系统调用栈的行为代码也更能体现出你对这个过程的真正理解。3.1 迭代版中序遍历的完整代码public ListInteger inorderTraversal(TreeNode root) { ListInteger result 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(); result.add(cur.val); cur cur.right; } return result; }这段代码的核心思路是从根节点开始把当前节点及其所有左子节点依次压入栈中。当cur为空时说明已经走到了当前子树的“最左边”此时从栈中弹出一个节点。弹出的节点就是要访问的节点把它的值加入结果集。然后将cur指向弹出节点的右子节点重复上述过程。用数据结构的语言来说栈中保存的是“等着处理右子树的节点”。每弹出一个节点就意味着它的左子树已经全部处理完了接下来该访问它本身再转向它的右子树。3.2 为什么用栈来实现而不是队列这里要说一个常见的困惑迭代遍历时不都是用栈吗为什么有的人用队列其实队列对应的是广度优先遍历BFS栈对应的才是深度优先遍历DFS。中序、前序、后序都属于DFS所以用栈。这一点如果搞混了代码是无论如何也写不对的。迭代版中序遍历的空间复杂度是O(h)其中h为树的高度。最坏情况下链状树栈中会同时存储n个节点空间复杂度为O(n)。这里有一个优化小经验如果面试官要求“只能用O(1)额外空间”那就得转向Morris遍历了这个在后文会详细说明。3.3 迭代写法的一个易错点很多人在迭代写法里犯的错误是没有把cur在出栈后置为cur.right导致死循环。每次从栈中弹出节点并访问后一定要将cur更新为该节点的右孩子。如果右孩子为空下一次循环就不会进入内层的while (cur ! null)而是直接从栈中弹出一个新的节点。这个“回退”的机制正是迭代模拟递归的精髓。我遇到过一些初学者他们会问“为什么弹出的节点不需要再压回栈”答案是栈里存的是“当前已经访问完左子树的节点”弹出的节点已经轮到访问自身了访问完之后它的整个左子树和自身都处理完毕接下来只需要处理右子树即可。如果再把自身压回栈那就会导致无限循环。4. Morris遍历把空间复杂度压到O(1)的黑科技Morris遍历可能不是每个人都会在面试中遇到但它经常被作为压轴问题出现。它利用二叉树中大量存在的空指针空右指针来记录回溯路径从而省掉了栈把空间复杂度降到了O(1)。4.1 Morris遍历的核心思想Morris中序遍历的基本思路是对每个当前节点找到它的左子树中“最右边”的节点也就是中序遍历中当前节点的前驱节点。如果这个前驱节点的右指针为空就把它的右指针指向当前节点形成一个临时的回路如果前驱节点的右指针已经指向当前节点说明左子树已经处理完毕此时断开这个临时链接恢复树的原始结构再访问当前节点并转向右子树。整个遍历过程里树的结构会被临时修改但遍历完成后会被完全恢复。这也是Morris遍历的独特之处。4.2 Morris中序遍历的Java实现public ListInteger inorderTraversal(TreeNode root) { ListInteger result new ArrayList(); TreeNode cur root; while (cur ! null) { if (cur.left null) { result.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; result.add(cur.val); cur cur.right; } } } return result; }值得单独说明的是查找前驱节点的那个while循环。它会在左子树里一路向右直到找到一个没有右孩子或者右孩子已经指向当前节点的节点。这里有两个终止条件一是predecessor.right null说明还没建立回溯链接说明当前节点是第一次到达此时将前驱节点的右指针指向当前节点然后继续往左深入二是predecessor.right cur说明之前已经建立过链接此时左子树已经走完了需要断开链接恢复原状然后访问当前节点。这里有一个很容易出错的点在查找前驱节点的循环中predecessor.right ! cur这个条件不能省略。如果没有这个条件当predecessor.right已经被修改为当前节点时循环将永远找不到退出条件导致死循环。我最初写Morris遍历时也犯过这个错误后来画图才发现如果没有这个判断第二次经过节点时就会无限向右遍历。4.3 时间复杂度为什么仍然是O(n)很多人觉得Morris遍历里需要反复找前驱节点肯定不是O(n)。但严谨的分析会说明虽然每个节点可能被“找前驱”的过程多次经过但每个左子树的右链至多被访问两次整体摊还下来的时间复杂度仍然是O(n)。它不是O(n log n)更不是O(n^2)这一点是Morris遍历能够作为“最优解”被认可的原因。在实际工程中除了面试外Morris遍历用得并不多因为它会修改树的结构在并发或多线程场景下很不安全调试也相对困难。但它的设计思想非常值得学习理解了Morris遍历的临时线索机制对理解“如何利用空指针”会有很深的启发。5. 中序遍历的实战应用与变形题中序遍历不只是一道孤立的基础题它和不少经典算法题目有紧密联系。5.1 验证二叉搜索树一道经典的面试题是给定一棵二叉树判断它是否是二叉搜索树BST。常规解法之一就是利用BST中序遍历严格递增的性质。对当前树做中序遍历然后检查结果序列是否严格递增即可。public boolean isValidBST(TreeNode root) { ListInteger list new ArrayList(); inorder(root, list); for (int i 1; i list.size(); i) { if (list.get(i) list.get(i - 1)) { return false; } } return true; }这个做法的优点是直观缺点是必须保存整个序列空间复杂度是O(n)。可以优化为在中序遍历的过程中记录上一个访问的节点值一旦当前值不大于上一个值就立即返回false。5.2 第K小的元素在二叉搜索树中查找第K小的元素最常见的思路就是用中序遍历。因为中序遍历的第K个访问节点就是第K小的节点。用迭代实现时可以在弹出节点时计数计数达到K时直接返回不需要遍历整棵树。5.3 中序遍历与其他遍历序列的互相推导另一类常见的变形题是给定前序遍历和中序遍历序列要求重构二叉树。这类题之所以能解是因为前序遍历确定了根节点的位置而中序遍历能够根据根节点位置把序列分成左子树范围和右子树范围。所以掌握中序遍历的本质也是解决这类重构题的前提。6. 常见问题与排查技巧实录6.1 空指针与边界条件处理二叉树问题时最容易出现的就是空指针异常。比如在递归版本里如果root为空直接返回空列表就行不需要额外处理。在迭代版本中判断循环条件时要用cur ! null || !stack.isEmpty()而不是只判断cur ! null否则当树为空时栈为空且循环直接不执行结果倒是对的但如果树只有右子树且一开始cur不为空也可能出现循环提前退出的问题。6.2 递归栈溢出的实验与对策为了验证递归版本的风险我试过构造一棵深度为1万左右的退化树在普通的JVM参数下跑递归中序遍历结果是直接抛出StackOverflowError。这算是一个比较有冲击力的实验。遇到这种情况常见的对策有三个将递归改成迭代写法使用显式栈。增加JVM栈大小如使用-Xss10m参数但这只是治标不治本。改用Morris遍历将空间复杂度降为O(1)。6.3 三种实现方式的对比速查表实现方式时间复杂度空间复杂度是否修改树结构是否推荐用于生产递归O(n)O(h)最坏O(n)否适合浅树迭代显式栈O(n)O(h)最坏O(n)否推荐MorrisO(n)O(1)遍历过程中临时修改遍历后恢复仅在特殊场景使用6.4 面试时的答题策略在面试场景下我建议的答题顺序是先快速给出递归版本并准确说出时间复杂度和空间复杂度然后主动补充迭代版本说明它解决了递归可能带来的栈溢出问题如果面试官继续追问“能不能做到O(1)空间”再给出Morris遍历的代码。这样层层递进既能展示基础掌握程度也能体现知识深度。很多人在面试时容易犯一个错误一开始就直接写Morris遍历认为这是最优解。但实际上如果面试官期望的是递归和迭代代码会显得冗长反而容易被追问到细节上卡壳。先给简单方案再逐步优化是最稳妥的策略。7. 一个更全面的工具方法统一迭代模板有些人在学习和面试中会遇到一个困惑前序、中序、后序的迭代写法每次都得分三种思路去记容易把顺序搞混。其实可以用一种统一的迭代模板来记忆本质上是把栈中需要“访问”的节点用标记位区分。不过我个人在实际使用中发现统一的迭代模板确实方便记忆但性能上略优于递归略逊于专门针对中序遍历的迭代写法。因为统一模板在每个节点上都多了一次标记值的压栈和判断。如果你的目标是面试中快速输出统一模板是一个不错的选择但如果你追求最优实现还是推荐单独写中序迭代。public ListInteger inorderTraversal(TreeNode root) { ListInteger result new ArrayList(); DequeObject stack new ArrayDeque(); if (root ! null) { stack.push(root); } while (!stack.isEmpty()) { Object top stack.pop(); if (top instanceof TreeNode) { TreeNode node (TreeNode) top; stack.push(node.right); stack.push(node.val); stack.push(node.left); } else { result.add((Integer) top); } } return result; }注意这里我故意写了一种简化示意但在实际Java编码中把节点值和标记位都压入同一个栈时通常需要定义辅助包装类或者用Object类型做判断。一般不太推荐在代码里大量使用Object类型安全会受影响也不利于后续维护。所以这个模板仅供理解思路真正生产代码我更推荐前面写的标准迭代版。8. 个人实操体会与后备方案我自己在实际刷题和面试中反复写中序遍历后最大的体会是中序遍历的价值远远不止于“背出代码”。它涉及递归与栈的联系、树结构与空间复杂度的权衡以及如何利用树空指针来优化空间。这些思想和技巧会直接迁移到很多更复杂的二叉树题目比如最近公共祖先、二叉树展开为链表、重建二叉树等。如果刷这道题我建议按这样的路径来练习先手写递归版直到不需要思考就能写出。再手写迭代版并亲手模拟一遍栈的变化过程推荐画图帮助理解。最后看是否有兴趣挑战Morris遍历重点理解它为什么能保持O(n)的时间复杂度。在每个版本里都加入中序遍历的实际应用测试例如在BST上求第K小元素验证代码正确性。最后分享一个小技巧如果想快速验证自己写的遍历代码是否正确可以自己构造一棵简单的平衡二叉树然后在纸上写出中序遍历的预期结果再拿输出对比。这个方法虽然朴素但排查起来非常高效尤其能帮你发现边界条件处理不当的问题。掌握了这道经典题二叉树相关面试题的底气基本就有了。