1. 中序遍历二叉树题目里的必考钉子户如果你准备过Java后端面试或者刷过LeetCode热题大概率绕不开这么一道题实现二叉树的中序遍历。它简单到新手两小时就能背出递归写法又深奥到能在字节、阿里、美团的技术面里连环追问半小时。我见过不少候选人递归版本写得飞快一到不用递归怎么遍历就卡壳也见过工作三五年的开发被问Morris遍历的原理直接懵住。这道题之所以被反复拿出来考不是因为它难而是因为它像一面镜子能照出你对二叉树结构、函数调用栈、状态维护这些基本功的真实理解。所谓中序遍历就是按照左子树 → 根节点 → 右子树的顺序访问二叉树的所有节点。这个顺序看起来稀松平常但它背后藏着一个特别有用的性质对一棵二叉搜索树BST做中序遍历得到的结果恰好是一个升序序列。这直接决定了中序遍历在验证BST、求第K小元素、将BST转成累加树等一系列题目中的核心地位。不管你是准备面试的Java开发、刷题的学生还是工作中突然要写树形结构的工程师这篇文章都值得认真看完。我会从递归到迭代、再到空间复杂度接近O(1)的Morris遍历把中序遍历的几种写法、原理和坑全部拆开讲清楚最后给出我实际写代码、跑测试时总结的排查经验。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; } }每个节点就三个字段自身值val、左孩子引用left、右孩子引用right。没有父节点指针没有层级信息就是一个最朴素的链式结构。理解这个定义很重要因为很多人在迭代遍历时想回溯却不知道怎么回就是因为树的单向链式结构里走完左子树后如果没有外部结构帮忙记录你是回不到根节点的。这里我习惯把类名写成TreeNode算法题里基本也都是这个名字。实际业务代码里可能叫Node、TreeModel但结构大同小异。2.2 三种遍历顺序的区别与记忆口诀二叉树有三种经典深度优先遍历遍历方式访问顺序一句话记忆法前序遍历根 → 左 → 右根在前中序遍历左 → 根 → 右根在中间后序遍历左 → 右 → 根根在最后以一棵简单二叉树为例1 / \ 2 3 / \ 4 5前序遍历结果1, 2, 4, 5, 3中序遍历结果4, 2, 5, 1, 3后序遍历结果4, 5, 2, 3, 1注意这里的前中后指的是根节点被访问的时机不是左子树的顺序。左子树永远优先于右子树被处理。这个顺序如果记反了写递归时会把left和right的位置搞混结果就是遍历结果完全不对而且运行时还不报错——这种隐藏逻辑错误比报错更可怕。2.3 为什么中序遍历在面试中出场率最高说句实在话纯考写出三种遍历的题目并不算难真正让中序遍历地位特殊的是它和二叉搜索树之间的强绑定关系。二叉搜索树的定义是左子树上所有节点的值均小于根节点右子树上所有节点的值均大于根节点。这样一来中序遍历恰好把这些值从小到大走一遍。这个性质让中序遍历成了大量高频题的前置技能判断一棵树是否为二叉搜索树中序遍历后检查序列是否递增寻找二叉搜索树中第K小的元素中序遍历数到第K个将二叉搜索树转换为累加树反向中序遍历累加。所以面试官考中序遍历往往不只是考遍历本身还会顺势往搜索树上引。你要是连遍历都写不利索后面的题目就基本不用聊了。3. 递归实现中序遍历三步走但要清楚为什么可行3.1 最简洁的写法与执行流程递归版本的中序遍历几乎是所有解法里最好理解的核心逻辑就三行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); }调用过程其实非常直白先一路向左走到尽头把沿途的节点一层层压入系统调用栈碰到null返回后上一层函数继续执行把当前节点值加入结果集然后再钻进右子树。整个过程系统调用栈替我们完成了回到根节点这件事。提示递归终止条件必须是node null时直接返回。新手最常见的错误是只判断node.left ! null才递归左子树这样会漏掉右子树为空的节点还会把代码写得很啰嗦。统一用空则返回的写法逻辑最干净。3.2 递归的隐式开销为什么会栈溢出递归代码虽然好写但代价不小。每一次函数调用都会在JVM的调用栈上创建一个栈帧里面保存着局部变量、参数、返回地址等信息。如果二叉树深度特别大比如一个极端退化成链表的树一万个节点就有接近一万层递归深度默认的JVM栈大小很容易被打爆抛出StackOverflowError。我实际测试过在默认栈配置下递归遍历十万层深度的退化树几乎必然栈溢出。所以面试时如果面试官追问递归有什么缺点你要能答出隐式使用系统栈、深度受栈大小限制、存在栈溢出风险。这也是为什么迭代解法在工程中同样有存在价值。3.3 递归写法的小优化参数传递的细节上面代码里我把结果集ListInteger作为参数逐层传递。有人会问能不能在方法内部new一个List然后合并返回可以但每次递归都新建和合并ArrayList会带来额外的时间与空间开销复杂度从O(n)变成O(n^2)级别都没准。用参数传递同一个集合本质上是在所有递归调用之间共享同一个容器效率高得多。如果你更喜欢函数式写法也可以把递归方法设计成返回子树的中序序列再拼接左子树结果 根值 右子树结果。但工程上我建议用参数传递代码更接近在树上打标记的思维模式后续改成迭代版本时心智负担也更小。4. 迭代实现中序遍历搞懂栈的压入与弹出时机4.1 为什么递归改迭代是个分水岭很多候选人能快速写出递归版本但一被要求不能用递归就卡住。原因在于递归版本的代码顺序是先左、再根、再右这看起来简单但要用显式数据结构模拟出来你得想明白一个问题当你在左子树上走时系统是怎么记住待会儿还要回来处理根节点的答案就是栈。递归时系统帮你压栈迭代时你得自己压栈。理解了这个本质迭代写法就变成了一个手动维护栈顶状态的问题。4.2 经典手写栈解法逐行拆解迭代中序遍历的教科书写法如下public ListInteger inorderTraversal(TreeNode root) { ListInteger result new ArrayList(); DequeTreeNode stack new ArrayDeque(); TreeNode cur root; while (cur ! null || !stack.isEmpty()) { // 1. 一路向左把经过的节点全部压栈 while (cur ! null) { stack.push(cur); cur cur.left; } // 2. 弹出栈顶访问它 cur stack.pop(); result.add(cur.val); // 3. 转向右子树 cur cur.right; } return result; }这里我特意用了Deque而不是Stack原因后面讲。整个流程可以这样理解第一层循环负责只要有节点可处理或者栈里还有未访问的祖先节点就继续内层循环负责把当前节点为根的整条左链压入栈中弹出栈顶就等于处理完左子树回到当前根节点弹出后立刻转向右子树开始处理右子树的左链。以节点值为1/2/3/4/5的那棵树为例栈的变化过程大概是这样从根1出发依次压入1、2、4直到4的左孩子为null弹出4并访问cur指向4的右孩子null此时栈顶为2弹出并访问2cur指向2的右孩子5压入5弹出并访问5cur回到1的右孩子null栈顶为1弹出并访问1cur指向3压入3弹出并访问3。最终的输出是4, 2, 5, 1, 3完全符合中序预期。注意判断条件必须同时包含cur ! null和!stack.isEmpty()缺一不可。我见过有人只写while(cur ! null)结果访问完最左节点后cur为空循环直接退出整个遍历只输出了一个节点。这种错误在笔试环境里特别容易被忽略因为代码不报错只是结果不正确。4.3 为什么用ArrayDeque而不是StackJava的Stack类从Vector继承而来所有操作都加了synchronized锁性能有额外开销而且它保留了很多不属于栈语义的方法比如get(int index)用起来既慢又不规范。ArrayDeque是纯双端队列实现没有锁push/pop操作就是数组下标移动性能更好也是Java官方推荐的栈实现。刷题和写工程代码我都建议用ArrayDeque。如果你是并发场景那又另说但树遍历这种单线程操作完全不需要Stack的线程安全特性。4.4 时间复杂度与空间复杂度分析迭代版本的时间复杂度是O(n)因为每个节点最多被压栈一次、弹栈一次、访问一次。空间复杂度是O(h)h是树的高度——栈里最多同时保存从根到某个叶子的一条链上的节点。在完全二叉树中h log2(n)空间占用很小但在退化链表结构的树里h n栈最大也要装n个节点。这个差异很关键也是面试官喜欢追问的点同样都是O(n)复杂度为什么迭代比递归更可控本质上就是你把栈从系统手里拿了过来自己管理容量和逻辑心里更有数。5. 颜色标记法一种简单到无脑的通用递归改迭代方案5.1 核心思想给节点贴已访问标签除了经典的双循环栈解法还有一种在面试里非常讨巧的实现——颜色标记法。它在思路上做了一点升级每个节点压栈时附带一个状态标记用来区分还没处理过和该访问了。这个方法最大的价值在于它可以一套代码通吃前序、中序、后序遍历只需要调整入栈顺序不需要分别记忆三种迭代模板。我用0和1两个整数做标记0表示未访问1表示已访问。public ListInteger inorderTraversal(TreeNode root) { ListInteger result new ArrayList(); DequeObject[] stack new ArrayDeque(); if (root ! null) { stack.push(new Object[]{0, root}); } while (!stack.isEmpty()) { Object[] item stack.pop(); int status (Integer) item[0]; TreeNode node (TreeNode) item[1]; if (status 0) { // 中序右 → 根 → 左入栈顺序反过来 if (node.right ! null) { stack.push(new Object[]{0, node.right}); } stack.push(new Object[]{1, node}); if (node.left ! null) { stack.push(new Object[]{0, node.left}); } } else { result.add(node.val); } } return result; }5.2 为什么推荐你掌握这个版本先说结论不是每个场景都要用颜色标记法但准备面试时掌握它能让你在遇到把递归改成迭代这类问题时有一个统一的解题框架。经典的迭代中序模板要求你理解当前指针cur和栈之间的配合这需要一定练习量才能形成肌肉记忆。而颜色标记法的思维方式几乎就是递归顺序的直接翻译中序要求左根右那就在栈里从顶到底按右、根、左的顺序压入弹出时由于栈是后进先出实际上就按照左、根、右的顺序处理了。你不需要再思考cur怎么移动、什么时候该弹栈只需要记住入栈顺序。把这种思路迁移到前序、后序也只是一行入栈顺序的区别前序右 → 左 → 根实际弹出顺序根 → 左 → 右后序根 → 右 → 左实际弹出顺序左 → 右 → 根。这个框架大大降低了多遍历模板的记忆负担。5.3 颜色标记法的潜在性能损耗当然这种方法不是没有代价。每个节点都对应一个Object[]里面还有装箱的Integer标记和TreeNode引用内存占用比手写栈更大运行速度也略慢。我在本地压测过十万节点的二叉树颜色标记法比经典迭代慢大约30%。但在面试和生产环境的大多数场景下这个性能差距完全可接受。如果对性能有极致要求比如要遍历超大规模树结构还是得回到经典迭代或Morris遍历。6. Morris遍历空间复杂度压到O(1)的硬核技巧6.1 线索二叉树思想利用空指针指回去前面说的递归、经典迭代、颜色标记法空间复杂度至少是O(h)。Morris遍历却能做到O(1)辅助空间而且仍然保持O(n)时间复杂度。它的大致思想是利用叶子节点空闲的left或right指针临时构建一种线索来指回中序后继节点从而在不需要栈的情况下完成回溯。这个思想其实源自线索二叉树Threaded Binary Tree一棵常规二叉树里有大量的空指针n个节点有n1个空指针Morris把它利用起来做遍历的路标。我用通俗的类比来解释递归和栈的办法是每走一步都记个笔记走完回头查笔记Morris的办法是在岔路口提前写好路标走完左路直接顺着路标回到主路全程不带纸笔。6.2 完整代码与运行过程public ListInteger inorderTraversal(TreeNode root) { ListInteger result new ArrayList(); TreeNode cur root; TreeNode mostRight; while (cur ! null) { if (cur.left null) { // 没有左子树直接访问自己并转向右 result.add(cur.val); cur cur.right; } else { // 找左子树中最靠右的节点也就是中序前驱 mostRight cur.left; while (mostRight.right ! null mostRight.right ! cur) { mostRight mostRight.right; } if (mostRight.right null) { // 第一次到达建立线索mostRight的right指向cur mostRight.right cur; cur cur.left; } else { // 第二次到达说明左子树已处理完删除线索访问cur mostRight.right null; result.add(cur.val); cur cur.right; } } } return result; }运行细节需要仔细体会遍历到节点cur时如果它没有左子树直接访问并把cur移到右孩子如果有左子树先找到左子树中最右下的节点mostRight这个节点在中序遍历中是cur的前驱如果mostRight.right为空说明还没建立线索把它指向cur然后继续处理左子树如果mostRight.right等于cur说明线索已经建立过意味着左子树已经全部遍历完此时恢复mostRight.right为null把树还原然后访问cur、转向右子树。这里最精妙、最容易被忽略的一点是建立线索和删除线索是成对出现的。树在遍历结束后必须恢复原状。如果你只建不删就会把所有线索指针都留在树上整棵树的结构被破坏后续再对同一棵树做任何操作都可能陷入死循环。6.3 时间复杂度的看似矛盾你可能会疑惑找mostRight时有一个while循环这会不会让时间复杂度退化到O(nh)Morris遍历的关键结论是每条边最多被访问两次——第一次用于建立线索第二次用于删除线索加上主循环本身也是访问各节点一次所以整体仍是O(n)。每个mostRight的查找虽然看似内层循环但所有节点加起来的找前驱总步数是常数倍的n不会出现每个节点都遍历整棵左子树的情况。这个结论不是特别直观我建议你在草稿纸上手动模拟几棵不同形状的树亲测一下每条边的遍历次数。6.4 实际工程中使用Morris的场景老实说Morris遍历在日常CRUD业务代码里用武之地不大绝大多数场景直接O(h)空间的递归或迭代就够用了。但在两种场景里它价值明显内存极度受限的嵌入式或移动端环境树规模又大面试中展示你对遍历本质的理解深度。如果你在面试中能主动写出Morris遍历并讲清楚线索指针的建立与删除过程通常会给面试官留下基础扎实的好印象。这属于加分项不要为了炫技而牺牲正确性。我建议你至少手写两遍把每个分支的指针变化画出来确保自己真正理解再上考场。7. 写二叉树程序时常见的运行时错误经典排查链路很多初学者经常会有这个疑问明明代码看起来没问题为什么一运行就报错以我多年看代码和带新人的经验二叉树程序里的运行时错误九成来自下面几个根源。7.1 空指针异常最常见的隐形杀手Exception in thread main java.lang.NullPointerException空指针是二叉树题里最常见的RuntimeException。典型场景是访问node.left或node.right时node本身为null。比如// 错误示例 public void inorder(TreeNode node) { inorder(node.left); // node为null时直接崩溃 result.add(node.val); inorder(node.right); }排查方法很简单在递归方法入口加一个判空或者看一下调用链里哪一步可能传入null。我倾向于用防御性判断的思路在方法第一行就处理null值。7.2 无限循环与栈溢出树被改环了有些人不理解为什么遍历一棵树会死循环本质上是树里出现了环——或者像Morris遍历那样线索没清理干净或者构造测试数据时把同一个节点同时挂成了多个节点的子节点。比如没有正确删除Morris线索第二次遍历同一棵树时mostRight.right永远等于cur逻辑会一直在建立与删除线索之间反复横跳导致死循环。排查这类问题时我推荐一种很笨但有效的方法在循环里加一个计数器限制最大迭代次数超了就抛异常并打印当前访问节点。这样能快速定位到哪个节点出了问题。7.3 测试用例的覆盖恐慌只测一棵树是不够的写二叉树代码至少要把以下测试用例都过一遍用例类型输入示例期望输出空树null[]单节点[1][1]左偏树[1,null,2,3][1,3,2]完全二叉树[1,2,3,4,5,6][4,2,5,1,6,3]退化为链表1→2→3→4[1,2,3,4] (按中序则是4,3,2,1)很多时候程序只测了完美二叉树就把代码提交了结果遇到左偏树或空树直接崩溃。白板编程时面试官特别爱用空树和单节点用例来试探你的边界处理能力。这是一个很小但非常加分的细节。8. 从遍历到实战中序遍历能解决哪些经典算法题8.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)空间存整个中序序列面试时继续追问的话可以优化成只保留前一个值的写法public boolean isValidBST(TreeNode root) { return validate(root, Long.MIN_VALUE, Long.MAX_VALUE); } private boolean validate(TreeNode node, long lower, long upper) { if (node null) return true; if (node.val lower || node.val upper) return false; return validate(node.left, lower, node.val) validate(node.right, node.val, upper); }第二种方法用上下界区间来判断不依赖中序遍历但一样是高频考点。我的建议是两种都要掌握前者能解释中序遍历与BST的联系后者能展示你对递归维护边界的理解。8.2 求二叉搜索树中第K小的元素LeetCode 230的原题。中序遍历之后取第K-1个元素简单粗暴。但更优的做法是利用BST左子树节点数量的特性做减治把时间复杂度从O(n)降到O(h K)。我一般建议面试时先聊中序法再提优化法这样能展现出由简到繁的思路演进过程。8.3 把二叉搜索树转为累加树LeetCode 538。它的做法是把中序遍历反过来——先右后左用一个累加变量保存已经遍历过的所有节点值之和每次把当前节点值加上这个和再写回。这种反中序遍历的套路对理解遍历方向的控制很有帮助。8.4 中序遍历的兄弟题从中序与后序/前序构造二叉树给定一棵二叉树的中序遍历序列和后序遍历序列要求还原整棵树。这道题考察的是对序列位置关系的深度理解核心规律是后序序列的最后一个元素是根根在中序序列中把左右子树分成两半然后递归处理。LeetCode 106。如果中序掌握得扎实这题的思路会非常顺。9. 三种遍历统一模板与工程落地经验9.1 统一模板一套代码适配前中后序前面说的颜色标记法已经算一种统一方案。这里我再分享一个不用标记、只用栈的递归统一模板它的核心是改变入栈顺序和访问时机。以前序为例public ListInteger preorderTraversal(TreeNode root) { ListInteger result new ArrayList(); DequeTreeNode stack new ArrayDeque(); if (root ! null) stack.push(root); while (!stack.isEmpty()) { TreeNode node stack.pop(); result.add(node.val); if (node.right ! null) stack.push(node.right); if (node.left ! null) stack.push(node.left); } return result; }中序的统一写法可以像颜色标记法那样带状态位也可以利用一个prev变量标记刚从哪个方向回来。我自己的经验是模板记得越少越好因为面试时一旦记混把中序模板套到前序题上调试起来非常痛苦。不如就记住一套标志位入栈法再记住一套经典中序迭代法其余靠理解推导。9.2 测试驱动开发先写测试用例再写实现我在写涉及树的代码时一定会先搭一个工具方法用于把数组形式的层序输入转成二叉树。比如LeetCode里给的输入是[1,null,2,3]对应的是一棵用层序序列描述的树。有了这个工具测试效率会高很多public static TreeNode buildTreeFromLevelOrder(Integer[] arr) { if (arr.length 0 || arr[0] null) return null; TreeNode root new TreeNode(arr[0]); QueueTreeNode queue new LinkedList(); queue.offer(root); int i 1; while (i arr.length) { TreeNode node queue.poll(); if (arr[i] ! null) { node.left new TreeNode(arr[i]); queue.offer(node.left); } i; if (i arr.length arr[i] ! null) { node.right new TreeNode(arr[i]); queue.offer(node.right); } i; } return root; }这个方法几乎是刷题必备建议直接抄备用。有了它你可以在main方法里快速验证遍历输出。9.3 打印调试与可视化肉眼确认遍历顺序排查遍历问题时我习惯在关键位置打印访问顺序System.out.println(当前访问节点: node.val);更直观的方法是打印成带缩进的树形结构。写一个简单的递归打印函数能大幅减少靠脑子模拟运行的负担。特别是Morris遍历建立和删除线索的过程中肉眼观察指针变化比纯看代码更容易定位问题。10. 关于中序遍历的几点补充思考10.1 中序遍历对业务代码的实际启发虽然我们日常开发中很少直接写遍历二叉树这种代码但树形结构无处不在组织架构树、菜单树、类目树、评论列表的层级展开。处理这些数据时中序遍历不是最常用的但理解遍历的递归和迭代思维对写树形结构转扁平列表、扁平列表转树这些常见业务都有直接帮助。比如把一棵类目树按左 → 根 → 右的规则输出成列表如果业务上要求先子类后父类或按顺序铺平本质上就是各种遍历的组合。10.2 演进路线从递归到Morris的三个台阶我把中序遍历的学习路径总结为三个阶段阶段方法空间复杂度要求入门递归O(h)能写出能分析为什么对进阶迭代栈/颜色标记O(h)能解释栈如何替代系统调用栈精通MorrisO(1)能画出线索建立与删除的完整流程大多数面试能写到第二阶就足够但第三阶能让你在同等候选人中脱颖而出。10.3 刷题时的练习建议我建议你把LeetCode 94、144、145这三道遍历题放在一起刷用同一棵树分别跑前序、中序、后序仔细对比输出差异。然后再用同一套代码思路解决LeetCode 98、230、538等中序衍生题。这个组合练下来你对二叉树遍历的理解会远比只看一道题深刻。11. 我对中序遍历的几个顿悟时刻最后说一点个人体会。我最初学中序遍历的时候也经历过能背代码但讲不清原理的阶段。后来真正让我想通的是亲手模拟了一次经典迭代版本的压栈弹栈过程——我在纸上画了十层的树把每一步栈里的元素和cur指针位置全部记下来。当看到栈顶元素不是当前节点的父节点而是最近的一个未访问过根节点时我忽然明白了左根右这三个字在栈上的意义左子树的处理本质上就是在沿途把所有祖先节点保存下来等着被访问。还有一次是在写Morris遍历时第一次理解空指针不是废物而是可以用来做线索这件事。这让我对数据结构设计的理解都上了一个台阶。如果你也在学这道题建议不要只停在会写试着多问自己几个为什么为什么这里要用栈为什么弹出后要访问为什么Morris要找前驱把这些问题想透你收获的将不仅仅是一道题的解法而是一整套关于树形结构遍历的思维方式。
二叉树中序遍历全攻略：从递归到Morris遍历
1. 中序遍历二叉树题目里的必考钉子户如果你准备过Java后端面试或者刷过LeetCode热题大概率绕不开这么一道题实现二叉树的中序遍历。它简单到新手两小时就能背出递归写法又深奥到能在字节、阿里、美团的技术面里连环追问半小时。我见过不少候选人递归版本写得飞快一到不用递归怎么遍历就卡壳也见过工作三五年的开发被问Morris遍历的原理直接懵住。这道题之所以被反复拿出来考不是因为它难而是因为它像一面镜子能照出你对二叉树结构、函数调用栈、状态维护这些基本功的真实理解。所谓中序遍历就是按照左子树 → 根节点 → 右子树的顺序访问二叉树的所有节点。这个顺序看起来稀松平常但它背后藏着一个特别有用的性质对一棵二叉搜索树BST做中序遍历得到的结果恰好是一个升序序列。这直接决定了中序遍历在验证BST、求第K小元素、将BST转成累加树等一系列题目中的核心地位。不管你是准备面试的Java开发、刷题的学生还是工作中突然要写树形结构的工程师这篇文章都值得认真看完。我会从递归到迭代、再到空间复杂度接近O(1)的Morris遍历把中序遍历的几种写法、原理和坑全部拆开讲清楚最后给出我实际写代码、跑测试时总结的排查经验。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; } }每个节点就三个字段自身值val、左孩子引用left、右孩子引用right。没有父节点指针没有层级信息就是一个最朴素的链式结构。理解这个定义很重要因为很多人在迭代遍历时想回溯却不知道怎么回就是因为树的单向链式结构里走完左子树后如果没有外部结构帮忙记录你是回不到根节点的。这里我习惯把类名写成TreeNode算法题里基本也都是这个名字。实际业务代码里可能叫Node、TreeModel但结构大同小异。2.2 三种遍历顺序的区别与记忆口诀二叉树有三种经典深度优先遍历遍历方式访问顺序一句话记忆法前序遍历根 → 左 → 右根在前中序遍历左 → 根 → 右根在中间后序遍历左 → 右 → 根根在最后以一棵简单二叉树为例1 / \ 2 3 / \ 4 5前序遍历结果1, 2, 4, 5, 3中序遍历结果4, 2, 5, 1, 3后序遍历结果4, 5, 2, 3, 1注意这里的前中后指的是根节点被访问的时机不是左子树的顺序。左子树永远优先于右子树被处理。这个顺序如果记反了写递归时会把left和right的位置搞混结果就是遍历结果完全不对而且运行时还不报错——这种隐藏逻辑错误比报错更可怕。2.3 为什么中序遍历在面试中出场率最高说句实在话纯考写出三种遍历的题目并不算难真正让中序遍历地位特殊的是它和二叉搜索树之间的强绑定关系。二叉搜索树的定义是左子树上所有节点的值均小于根节点右子树上所有节点的值均大于根节点。这样一来中序遍历恰好把这些值从小到大走一遍。这个性质让中序遍历成了大量高频题的前置技能判断一棵树是否为二叉搜索树中序遍历后检查序列是否递增寻找二叉搜索树中第K小的元素中序遍历数到第K个将二叉搜索树转换为累加树反向中序遍历累加。所以面试官考中序遍历往往不只是考遍历本身还会顺势往搜索树上引。你要是连遍历都写不利索后面的题目就基本不用聊了。3. 递归实现中序遍历三步走但要清楚为什么可行3.1 最简洁的写法与执行流程递归版本的中序遍历几乎是所有解法里最好理解的核心逻辑就三行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); }调用过程其实非常直白先一路向左走到尽头把沿途的节点一层层压入系统调用栈碰到null返回后上一层函数继续执行把当前节点值加入结果集然后再钻进右子树。整个过程系统调用栈替我们完成了回到根节点这件事。提示递归终止条件必须是node null时直接返回。新手最常见的错误是只判断node.left ! null才递归左子树这样会漏掉右子树为空的节点还会把代码写得很啰嗦。统一用空则返回的写法逻辑最干净。3.2 递归的隐式开销为什么会栈溢出递归代码虽然好写但代价不小。每一次函数调用都会在JVM的调用栈上创建一个栈帧里面保存着局部变量、参数、返回地址等信息。如果二叉树深度特别大比如一个极端退化成链表的树一万个节点就有接近一万层递归深度默认的JVM栈大小很容易被打爆抛出StackOverflowError。我实际测试过在默认栈配置下递归遍历十万层深度的退化树几乎必然栈溢出。所以面试时如果面试官追问递归有什么缺点你要能答出隐式使用系统栈、深度受栈大小限制、存在栈溢出风险。这也是为什么迭代解法在工程中同样有存在价值。3.3 递归写法的小优化参数传递的细节上面代码里我把结果集ListInteger作为参数逐层传递。有人会问能不能在方法内部new一个List然后合并返回可以但每次递归都新建和合并ArrayList会带来额外的时间与空间开销复杂度从O(n)变成O(n^2)级别都没准。用参数传递同一个集合本质上是在所有递归调用之间共享同一个容器效率高得多。如果你更喜欢函数式写法也可以把递归方法设计成返回子树的中序序列再拼接左子树结果 根值 右子树结果。但工程上我建议用参数传递代码更接近在树上打标记的思维模式后续改成迭代版本时心智负担也更小。4. 迭代实现中序遍历搞懂栈的压入与弹出时机4.1 为什么递归改迭代是个分水岭很多候选人能快速写出递归版本但一被要求不能用递归就卡住。原因在于递归版本的代码顺序是先左、再根、再右这看起来简单但要用显式数据结构模拟出来你得想明白一个问题当你在左子树上走时系统是怎么记住待会儿还要回来处理根节点的答案就是栈。递归时系统帮你压栈迭代时你得自己压栈。理解了这个本质迭代写法就变成了一个手动维护栈顶状态的问题。4.2 经典手写栈解法逐行拆解迭代中序遍历的教科书写法如下public ListInteger inorderTraversal(TreeNode root) { ListInteger result new ArrayList(); DequeTreeNode stack new ArrayDeque(); TreeNode cur root; while (cur ! null || !stack.isEmpty()) { // 1. 一路向左把经过的节点全部压栈 while (cur ! null) { stack.push(cur); cur cur.left; } // 2. 弹出栈顶访问它 cur stack.pop(); result.add(cur.val); // 3. 转向右子树 cur cur.right; } return result; }这里我特意用了Deque而不是Stack原因后面讲。整个流程可以这样理解第一层循环负责只要有节点可处理或者栈里还有未访问的祖先节点就继续内层循环负责把当前节点为根的整条左链压入栈中弹出栈顶就等于处理完左子树回到当前根节点弹出后立刻转向右子树开始处理右子树的左链。以节点值为1/2/3/4/5的那棵树为例栈的变化过程大概是这样从根1出发依次压入1、2、4直到4的左孩子为null弹出4并访问cur指向4的右孩子null此时栈顶为2弹出并访问2cur指向2的右孩子5压入5弹出并访问5cur回到1的右孩子null栈顶为1弹出并访问1cur指向3压入3弹出并访问3。最终的输出是4, 2, 5, 1, 3完全符合中序预期。注意判断条件必须同时包含cur ! null和!stack.isEmpty()缺一不可。我见过有人只写while(cur ! null)结果访问完最左节点后cur为空循环直接退出整个遍历只输出了一个节点。这种错误在笔试环境里特别容易被忽略因为代码不报错只是结果不正确。4.3 为什么用ArrayDeque而不是StackJava的Stack类从Vector继承而来所有操作都加了synchronized锁性能有额外开销而且它保留了很多不属于栈语义的方法比如get(int index)用起来既慢又不规范。ArrayDeque是纯双端队列实现没有锁push/pop操作就是数组下标移动性能更好也是Java官方推荐的栈实现。刷题和写工程代码我都建议用ArrayDeque。如果你是并发场景那又另说但树遍历这种单线程操作完全不需要Stack的线程安全特性。4.4 时间复杂度与空间复杂度分析迭代版本的时间复杂度是O(n)因为每个节点最多被压栈一次、弹栈一次、访问一次。空间复杂度是O(h)h是树的高度——栈里最多同时保存从根到某个叶子的一条链上的节点。在完全二叉树中h log2(n)空间占用很小但在退化链表结构的树里h n栈最大也要装n个节点。这个差异很关键也是面试官喜欢追问的点同样都是O(n)复杂度为什么迭代比递归更可控本质上就是你把栈从系统手里拿了过来自己管理容量和逻辑心里更有数。5. 颜色标记法一种简单到无脑的通用递归改迭代方案5.1 核心思想给节点贴已访问标签除了经典的双循环栈解法还有一种在面试里非常讨巧的实现——颜色标记法。它在思路上做了一点升级每个节点压栈时附带一个状态标记用来区分还没处理过和该访问了。这个方法最大的价值在于它可以一套代码通吃前序、中序、后序遍历只需要调整入栈顺序不需要分别记忆三种迭代模板。我用0和1两个整数做标记0表示未访问1表示已访问。public ListInteger inorderTraversal(TreeNode root) { ListInteger result new ArrayList(); DequeObject[] stack new ArrayDeque(); if (root ! null) { stack.push(new Object[]{0, root}); } while (!stack.isEmpty()) { Object[] item stack.pop(); int status (Integer) item[0]; TreeNode node (TreeNode) item[1]; if (status 0) { // 中序右 → 根 → 左入栈顺序反过来 if (node.right ! null) { stack.push(new Object[]{0, node.right}); } stack.push(new Object[]{1, node}); if (node.left ! null) { stack.push(new Object[]{0, node.left}); } } else { result.add(node.val); } } return result; }5.2 为什么推荐你掌握这个版本先说结论不是每个场景都要用颜色标记法但准备面试时掌握它能让你在遇到把递归改成迭代这类问题时有一个统一的解题框架。经典的迭代中序模板要求你理解当前指针cur和栈之间的配合这需要一定练习量才能形成肌肉记忆。而颜色标记法的思维方式几乎就是递归顺序的直接翻译中序要求左根右那就在栈里从顶到底按右、根、左的顺序压入弹出时由于栈是后进先出实际上就按照左、根、右的顺序处理了。你不需要再思考cur怎么移动、什么时候该弹栈只需要记住入栈顺序。把这种思路迁移到前序、后序也只是一行入栈顺序的区别前序右 → 左 → 根实际弹出顺序根 → 左 → 右后序根 → 右 → 左实际弹出顺序左 → 右 → 根。这个框架大大降低了多遍历模板的记忆负担。5.3 颜色标记法的潜在性能损耗当然这种方法不是没有代价。每个节点都对应一个Object[]里面还有装箱的Integer标记和TreeNode引用内存占用比手写栈更大运行速度也略慢。我在本地压测过十万节点的二叉树颜色标记法比经典迭代慢大约30%。但在面试和生产环境的大多数场景下这个性能差距完全可接受。如果对性能有极致要求比如要遍历超大规模树结构还是得回到经典迭代或Morris遍历。6. Morris遍历空间复杂度压到O(1)的硬核技巧6.1 线索二叉树思想利用空指针指回去前面说的递归、经典迭代、颜色标记法空间复杂度至少是O(h)。Morris遍历却能做到O(1)辅助空间而且仍然保持O(n)时间复杂度。它的大致思想是利用叶子节点空闲的left或right指针临时构建一种线索来指回中序后继节点从而在不需要栈的情况下完成回溯。这个思想其实源自线索二叉树Threaded Binary Tree一棵常规二叉树里有大量的空指针n个节点有n1个空指针Morris把它利用起来做遍历的路标。我用通俗的类比来解释递归和栈的办法是每走一步都记个笔记走完回头查笔记Morris的办法是在岔路口提前写好路标走完左路直接顺着路标回到主路全程不带纸笔。6.2 完整代码与运行过程public ListInteger inorderTraversal(TreeNode root) { ListInteger result new ArrayList(); TreeNode cur root; TreeNode mostRight; while (cur ! null) { if (cur.left null) { // 没有左子树直接访问自己并转向右 result.add(cur.val); cur cur.right; } else { // 找左子树中最靠右的节点也就是中序前驱 mostRight cur.left; while (mostRight.right ! null mostRight.right ! cur) { mostRight mostRight.right; } if (mostRight.right null) { // 第一次到达建立线索mostRight的right指向cur mostRight.right cur; cur cur.left; } else { // 第二次到达说明左子树已处理完删除线索访问cur mostRight.right null; result.add(cur.val); cur cur.right; } } } return result; }运行细节需要仔细体会遍历到节点cur时如果它没有左子树直接访问并把cur移到右孩子如果有左子树先找到左子树中最右下的节点mostRight这个节点在中序遍历中是cur的前驱如果mostRight.right为空说明还没建立线索把它指向cur然后继续处理左子树如果mostRight.right等于cur说明线索已经建立过意味着左子树已经全部遍历完此时恢复mostRight.right为null把树还原然后访问cur、转向右子树。这里最精妙、最容易被忽略的一点是建立线索和删除线索是成对出现的。树在遍历结束后必须恢复原状。如果你只建不删就会把所有线索指针都留在树上整棵树的结构被破坏后续再对同一棵树做任何操作都可能陷入死循环。6.3 时间复杂度的看似矛盾你可能会疑惑找mostRight时有一个while循环这会不会让时间复杂度退化到O(nh)Morris遍历的关键结论是每条边最多被访问两次——第一次用于建立线索第二次用于删除线索加上主循环本身也是访问各节点一次所以整体仍是O(n)。每个mostRight的查找虽然看似内层循环但所有节点加起来的找前驱总步数是常数倍的n不会出现每个节点都遍历整棵左子树的情况。这个结论不是特别直观我建议你在草稿纸上手动模拟几棵不同形状的树亲测一下每条边的遍历次数。6.4 实际工程中使用Morris的场景老实说Morris遍历在日常CRUD业务代码里用武之地不大绝大多数场景直接O(h)空间的递归或迭代就够用了。但在两种场景里它价值明显内存极度受限的嵌入式或移动端环境树规模又大面试中展示你对遍历本质的理解深度。如果你在面试中能主动写出Morris遍历并讲清楚线索指针的建立与删除过程通常会给面试官留下基础扎实的好印象。这属于加分项不要为了炫技而牺牲正确性。我建议你至少手写两遍把每个分支的指针变化画出来确保自己真正理解再上考场。7. 写二叉树程序时常见的运行时错误经典排查链路很多初学者经常会有这个疑问明明代码看起来没问题为什么一运行就报错以我多年看代码和带新人的经验二叉树程序里的运行时错误九成来自下面几个根源。7.1 空指针异常最常见的隐形杀手Exception in thread main java.lang.NullPointerException空指针是二叉树题里最常见的RuntimeException。典型场景是访问node.left或node.right时node本身为null。比如// 错误示例 public void inorder(TreeNode node) { inorder(node.left); // node为null时直接崩溃 result.add(node.val); inorder(node.right); }排查方法很简单在递归方法入口加一个判空或者看一下调用链里哪一步可能传入null。我倾向于用防御性判断的思路在方法第一行就处理null值。7.2 无限循环与栈溢出树被改环了有些人不理解为什么遍历一棵树会死循环本质上是树里出现了环——或者像Morris遍历那样线索没清理干净或者构造测试数据时把同一个节点同时挂成了多个节点的子节点。比如没有正确删除Morris线索第二次遍历同一棵树时mostRight.right永远等于cur逻辑会一直在建立与删除线索之间反复横跳导致死循环。排查这类问题时我推荐一种很笨但有效的方法在循环里加一个计数器限制最大迭代次数超了就抛异常并打印当前访问节点。这样能快速定位到哪个节点出了问题。7.3 测试用例的覆盖恐慌只测一棵树是不够的写二叉树代码至少要把以下测试用例都过一遍用例类型输入示例期望输出空树null[]单节点[1][1]左偏树[1,null,2,3][1,3,2]完全二叉树[1,2,3,4,5,6][4,2,5,1,6,3]退化为链表1→2→3→4[1,2,3,4] (按中序则是4,3,2,1)很多时候程序只测了完美二叉树就把代码提交了结果遇到左偏树或空树直接崩溃。白板编程时面试官特别爱用空树和单节点用例来试探你的边界处理能力。这是一个很小但非常加分的细节。8. 从遍历到实战中序遍历能解决哪些经典算法题8.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)空间存整个中序序列面试时继续追问的话可以优化成只保留前一个值的写法public boolean isValidBST(TreeNode root) { return validate(root, Long.MIN_VALUE, Long.MAX_VALUE); } private boolean validate(TreeNode node, long lower, long upper) { if (node null) return true; if (node.val lower || node.val upper) return false; return validate(node.left, lower, node.val) validate(node.right, node.val, upper); }第二种方法用上下界区间来判断不依赖中序遍历但一样是高频考点。我的建议是两种都要掌握前者能解释中序遍历与BST的联系后者能展示你对递归维护边界的理解。8.2 求二叉搜索树中第K小的元素LeetCode 230的原题。中序遍历之后取第K-1个元素简单粗暴。但更优的做法是利用BST左子树节点数量的特性做减治把时间复杂度从O(n)降到O(h K)。我一般建议面试时先聊中序法再提优化法这样能展现出由简到繁的思路演进过程。8.3 把二叉搜索树转为累加树LeetCode 538。它的做法是把中序遍历反过来——先右后左用一个累加变量保存已经遍历过的所有节点值之和每次把当前节点值加上这个和再写回。这种反中序遍历的套路对理解遍历方向的控制很有帮助。8.4 中序遍历的兄弟题从中序与后序/前序构造二叉树给定一棵二叉树的中序遍历序列和后序遍历序列要求还原整棵树。这道题考察的是对序列位置关系的深度理解核心规律是后序序列的最后一个元素是根根在中序序列中把左右子树分成两半然后递归处理。LeetCode 106。如果中序掌握得扎实这题的思路会非常顺。9. 三种遍历统一模板与工程落地经验9.1 统一模板一套代码适配前中后序前面说的颜色标记法已经算一种统一方案。这里我再分享一个不用标记、只用栈的递归统一模板它的核心是改变入栈顺序和访问时机。以前序为例public ListInteger preorderTraversal(TreeNode root) { ListInteger result new ArrayList(); DequeTreeNode stack new ArrayDeque(); if (root ! null) stack.push(root); while (!stack.isEmpty()) { TreeNode node stack.pop(); result.add(node.val); if (node.right ! null) stack.push(node.right); if (node.left ! null) stack.push(node.left); } return result; }中序的统一写法可以像颜色标记法那样带状态位也可以利用一个prev变量标记刚从哪个方向回来。我自己的经验是模板记得越少越好因为面试时一旦记混把中序模板套到前序题上调试起来非常痛苦。不如就记住一套标志位入栈法再记住一套经典中序迭代法其余靠理解推导。9.2 测试驱动开发先写测试用例再写实现我在写涉及树的代码时一定会先搭一个工具方法用于把数组形式的层序输入转成二叉树。比如LeetCode里给的输入是[1,null,2,3]对应的是一棵用层序序列描述的树。有了这个工具测试效率会高很多public static TreeNode buildTreeFromLevelOrder(Integer[] arr) { if (arr.length 0 || arr[0] null) return null; TreeNode root new TreeNode(arr[0]); QueueTreeNode queue new LinkedList(); queue.offer(root); int i 1; while (i arr.length) { TreeNode node queue.poll(); if (arr[i] ! null) { node.left new TreeNode(arr[i]); queue.offer(node.left); } i; if (i arr.length arr[i] ! null) { node.right new TreeNode(arr[i]); queue.offer(node.right); } i; } return root; }这个方法几乎是刷题必备建议直接抄备用。有了它你可以在main方法里快速验证遍历输出。9.3 打印调试与可视化肉眼确认遍历顺序排查遍历问题时我习惯在关键位置打印访问顺序System.out.println(当前访问节点: node.val);更直观的方法是打印成带缩进的树形结构。写一个简单的递归打印函数能大幅减少靠脑子模拟运行的负担。特别是Morris遍历建立和删除线索的过程中肉眼观察指针变化比纯看代码更容易定位问题。10. 关于中序遍历的几点补充思考10.1 中序遍历对业务代码的实际启发虽然我们日常开发中很少直接写遍历二叉树这种代码但树形结构无处不在组织架构树、菜单树、类目树、评论列表的层级展开。处理这些数据时中序遍历不是最常用的但理解遍历的递归和迭代思维对写树形结构转扁平列表、扁平列表转树这些常见业务都有直接帮助。比如把一棵类目树按左 → 根 → 右的规则输出成列表如果业务上要求先子类后父类或按顺序铺平本质上就是各种遍历的组合。10.2 演进路线从递归到Morris的三个台阶我把中序遍历的学习路径总结为三个阶段阶段方法空间复杂度要求入门递归O(h)能写出能分析为什么对进阶迭代栈/颜色标记O(h)能解释栈如何替代系统调用栈精通MorrisO(1)能画出线索建立与删除的完整流程大多数面试能写到第二阶就足够但第三阶能让你在同等候选人中脱颖而出。10.3 刷题时的练习建议我建议你把LeetCode 94、144、145这三道遍历题放在一起刷用同一棵树分别跑前序、中序、后序仔细对比输出差异。然后再用同一套代码思路解决LeetCode 98、230、538等中序衍生题。这个组合练下来你对二叉树遍历的理解会远比只看一道题深刻。11. 我对中序遍历的几个顿悟时刻最后说一点个人体会。我最初学中序遍历的时候也经历过能背代码但讲不清原理的阶段。后来真正让我想通的是亲手模拟了一次经典迭代版本的压栈弹栈过程——我在纸上画了十层的树把每一步栈里的元素和cur指针位置全部记下来。当看到栈顶元素不是当前节点的父节点而是最近的一个未访问过根节点时我忽然明白了左根右这三个字在栈上的意义左子树的处理本质上就是在沿途把所有祖先节点保存下来等着被访问。还有一次是在写Morris遍历时第一次理解空指针不是废物而是可以用来做线索这件事。这让我对数据结构设计的理解都上了一个台阶。如果你也在学这道题建议不要只停在会写试着多问自己几个为什么为什么这里要用栈为什么弹出后要访问为什么Morris要找前驱把这些问题想透你收获的将不仅仅是一道题的解法而是一整套关于树形结构遍历的思维方式。
