1. 为什么中序遍历值得单独拎出来讲二叉树遍历这个事说大不大说小也不小。但凡写过几行数据结构代码的人都能随手写出一个递归版本的中序遍历三行代码搞定闭着眼睛都能默写。但真正到了面试场景、到了实际工程里需要手动控制遍历过程的时候递归那套写法往往就不够用了。我见过太多同学递归写得飞起一让写非递归版本就卡壳要么栈的边界条件搞不清楚要么指针推进的逻辑写反了调半天调不通。这篇文章就围绕Java 二叉树中序遍历这个核心主题把递归和非递归两套方案从头到尾拆一遍。不光是给你代码更重要的是把每一步为什么这么写、栈里面到底存了什么、指针什么时候该动什么时候不该动这些容易含糊的地方讲透。适合正在准备面试的开发者、刚学数据结构的学生以及工作中偶尔需要手写遍历逻辑但不想每次都翻笔记的工程师。读完你至少能做到两件事第一白板上手写非递归中序不出错第二被追问“为什么用栈不用队列”“Morris遍历怎么把空间降到O(1)”的时候能答得上来。中序遍历的特殊性在于它的访问顺序——左、根、右。这个顺序决定了它不像前序遍历那样“遇到节点就能处理”也不像后序遍历那样“处理完子节点再回头处理根”。中序必须先把整条左链走到底才能开始处理第一个节点处理完又要能“回到”父节点继续走它的右子树。这个“回去”的动作就是递归天然帮你做的事也是非递归版本必须用栈手动模拟的核心原因。理解了这一点后面所有的代码都只是这个思路的翻译而已。2. 先把节点定义和测试树定下来2.1 二叉树节点的标准写法在Java里定义一个二叉树节点最朴素的方式就是一个静态内部类三个字段值、左孩子、右孩子。构造方法给一个值的重载就够了左右孩子默认null后续手动挂。public class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int val) { this.val val; } }这里有个小细节值得说一下字段用int还是Integer。如果题目保证节点值都是有效整数用int没问题省去装箱开销。但如果涉及“空节点用null表示”或者值可能为null的场景就得用Integer。我个人的习惯是刷题用int工程里如果节点值可能缺失用Integer更稳妥。另外字段的访问修饰符如果这个类只在当前包内用包级私有不写修饰符就够了如果要跨包老老实实写private加getter/setter或者直接用public图省事——刷题场景下public完全可接受别为了“规范”把代码搞得又臭又长。2.2 构造一棵有代表性的测试树光有节点定义不够得有一棵形状有特点的树来验证遍历结果。我习惯用下面这棵4 / \ 2 6 / \ / \ 1 3 5 7这是一棵满二叉树中序遍历结果是1 2 3 4 5 6 7正好是升序。用升序序列做验证有个好处结果对不对一眼就能看出来不用对着树一个个数。构造代码TreeNode buildTree() { TreeNode n1 new TreeNode(1); TreeNode n3 new TreeNode(3); TreeNode n5 new TreeNode(5); TreeNode n7 new TreeNode(7); TreeNode n2 new TreeNode(2); TreeNode n6 new TreeNode(6); TreeNode n4 new TreeNode(4); n2.left n1; n2.right n3; n6.left n5; n6.right n7; n4.left n2; n4.right n6; return n4; }注意构造顺序建议从叶子往根建先建好所有子节点再挂到父节点上。如果反过来先建根再建子节点容易在挂接的时候引用到还没初始化的变量虽然Java不会报编译错误但逻辑上容易乱。除了这棵满二叉树强烈建议再准备两棵“边界树”来测一棵只有左孩子的链状树比如1-2-3-4全在左边一棵只有右孩子的链状树。链状树是检验非递归代码栈处理是否正确的最佳试金石很多边界bug在满二叉树上跑不出来一上链状树就露馅。3. 递归版本三行代码背后的执行真相3.1 递归代码本身递归版本的中序遍历核心就三行public void inorderRecursive(TreeNode root, ListInteger result) { if (root null) { return; } inorderRecursive(root.left, result); result.add(root.val); inorderRecursive(root.right, result); }调用方式ListInteger result new ArrayList(); inorderRecursive(buildTree(), result); System.out.println(result); // [1, 2, 3, 4, 5, 6, 7]代码简单到没什么好解释的但“简单”恰恰是它容易让人产生错觉的地方。很多人觉得自己懂了递归其实只是记住了这三行的顺序一旦被问“递归调用栈里每一层在干什么”就说不清楚了。3.2 递归调用栈到底发生了什么拿上面那棵树举例从根节点4开始。第一次调用inorder(4)先不处理4直接递归到inorder(2)inorder(2)也不处理2递归到inorder(1)inorder(1)发现左孩子是null于是处理1然后递归右孩子null返回inorder(1)结束。这时候控制权回到inorder(2)处理2再递归inorder(3)处理3返回。控制权回到inorder(4)处理4然后递归右子树同样的逻辑处理5、6、7。整个过程里每个节点被“压栈”的时机是第一次访问到它的时候被“处理”的时机是它的左子树全部处理完之后。这个“压栈”和“处理”之间的时间差就是递归帮你自动保存的上下文。非递归版本要做的就是用显式的栈把这个上下文存起来。实操心得理解递归最好的方式不是盯着代码看而是拿纸画一遍调用栈。每进入一层画一个方框写上当前节点每返回一层划掉一个方框。画完一遍你对“栈里存的是还没处理完的节点”这句话会有完全不同的体感。3.3 递归的隐患栈溢出不是吓唬人递归写法的最大问题不是效率是深度。Java的方法调用栈默认大小跟JVM参数有关一般能撑几千层。如果树退化成一条链比如一万个节点全在左边递归深度就是一万直接StackOverflowError。我实测过在某些默认配置的环境下大概五六千层就开始报错了。所以递归版本适合什么场景树比较平衡、深度可控的场景。比如平衡二叉搜索树深度是log级别的一万个节点也就十几层随便递归。但如果数据来源不可控可能是用户上传的、可能是数据库里读出来的你没法保证它平衡那就得考虑非递归版本或者至少加个深度检查。4. 非递归版本用栈手动模拟递归4.1 核心思路拆解非递归中序的核心思路一句话沿着左链一路压栈压到null为止然后弹栈处理节点再转向右孩子重复这个过程。为什么是“一路压栈”因为中序要求先处理最左边的节点而最左边的节点藏在整条左链的末端。你从根出发不把沿途的节点存起来等处理完最左边那个之后就找不到回去的路了。栈就是用来存这条“回去的路”的。为什么弹栈之后要“转向右孩子”因为弹出来的节点它的左子树已经处理完了不然不会弹到它它自己也处理完了接下来按中序的顺序该处理它的右子树了。右子树可能为空那就继续弹下一个右子树不为空那就对右子树重复“一路压栈”的过程。4.2 完整代码与逐行注释public ListInteger inorderIterative(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 ! null || !stack.isEmpty()两个条件缺一不可。只写cur ! null当cur变成null但栈里还有节点时就提前退出了只写!stack.isEmpty()一开始栈是空的根节点还没压进去就退出了。第二个是cur cur.right之后不能直接处理要回到外层循环重新走“一路压栈”因为右孩子可能还有左子树。4.3 用测试树走一遍完整流程还是那棵树我用表格把每一步的状态列出来这样比纯文字描述清楚得多。步骤cur指向栈内容栈顶在右操作result14[4]4压栈cur2[]22[4, 2]2压栈cur1[]31[4, 2, 1]1压栈curnull[]4null[4, 2]弹1处理1cur1.rightnull[1]5null[4]弹2处理2cur2.right3[1, 2]63[4, 3]3压栈curnull[1, 2]7null[4]弹3处理3curnull[1, 2, 3]8null[]弹4处理4cur4.right6[1, 2, 3, 4]96[6]6压栈cur5[1, 2, 3, 4]105[6, 5]5压栈curnull[1, 2, 3, 4]11null[6]弹5处理5curnull[1, 2, 3, 4, 5]12null[]弹6处理6cur7[1, 2, 3, 4, 5, 6]137[7]7压栈curnull[1, 2, 3, 4, 5, 6]14null[]弹7处理7curnull[1, 2, 3, 4, 5, 6, 7]15null[]循环条件不满足结束[1, 2, 3, 4, 5, 6, 7]走完这一遍栈的作用就非常直观了它保存的是“当前节点处理完之后下一个该处理的节点是谁”。每次弹栈弹出来的就是当前子树里最左下的那个还没处理的节点。4.4 为什么用Deque而不是Stack代码里我用的是DequeTreeNode stack new ArrayDeque()而不是Java自带的Stack类。原因有两个第一Stack是继承自Vector的所有方法都加了synchronized单线程场景下纯属浪费第二Deque接口的push/pop/peek语义更清晰ArrayDeque底层是数组性能比Stack好一截。这是Effective Java里明确推荐的做法实际写代码时养成习惯就好。注意ArrayDeque不允许存null元素。如果你的树节点可能为null并且你想压进去会抛NullPointerException。不过正常逻辑下我们不会把null压栈压栈的都是有效节点所以这个问题一般不会遇到。5. 递归与非递归的对比选型5.1 性能与可读性对照维度递归版本非递归版本代码行数约6行约15行可读性极高一眼看懂中等需要理解栈的作用空间复杂度O(h)h为树高递归栈开销O(h)显式栈开销栈溢出风险树深时存在无堆内存足够大调试难度调用栈深断点跳来跳去状态清晰容易打日志适用场景平衡树、深度可控深度不可控、需要手动控制流程空间复杂度两者都是O(h)但常数不一样。递归的每一层调用栈开销比一个栈帧元素大所以同样深度下非递归更省内存。不过这个差异在大多数场景下可以忽略选型主要看深度是否可控。5.2 什么时候必须用非递归有三种情况我会毫不犹豫选非递归。第一种是树的深度不可控比如从外部数据源构建的树你没法保证它平衡。第二种是需要在遍历过程中做复杂的状态管理比如遍历到某个节点时要暂停、要记录额外信息、要根据条件跳过某些子树这时候显式栈比递归灵活得多。第三种是面试要求很多面试官会直接说“不要用递归”这时候没得选。反过来如果树是平衡的、逻辑简单、追求代码简洁递归版本完全够用没必要为了“显得高级”硬写非递归。我见过有人在一个深度不超过20的配置树上用非递归代码多了一倍维护成本上去了收益为零。工具选型要看场景不是越复杂越好。6. 进阶Morris遍历把空间降到O(1)6.1 Morris遍历的核心思想前面两种方案空间都是O(h)Morris遍历能做到O(1)靠的是一个巧妙的技巧利用叶子节点的空右指针临时指向它的中序后继节点。这样就不需要额外的栈来记录“回去的路”了路就藏在树本身的结构里。具体做法是对于当前节点cur如果它没有左孩子直接处理cur然后curcur.right。如果有左孩子就找到左子树里最右边的节点也就是cur在中序下的前驱如果这个前驱的右指针是null就把它指向cur然后curcur.left如果前驱的右指针已经指向cur了说明左子树已经遍历完了把这个指针恢复成null处理cur然后curcur.right。6.2 Morris中序代码实现public ListInteger inorderMorris(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 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; // 恢复树的原状 result.add(cur.val); cur cur.right; } } } return result; }6.3 Morris遍历的代价与适用性Morris遍历虽然空间是O(1)但它不是没有代价的。第一它在遍历过程中临时修改了树的结构虽然最后会恢复但如果遍历中途抛异常树就被改坏了。第二它的常数时间更大每个节点找前驱的过程要额外走一段路整体时间复杂度虽然还是O(n)但实际跑起来比栈版本慢。第三代码更难写对pre.right ! null pre.right ! cur这个条件少一个都会出问题。我的建议是面试时如果面试官追问“能不能不用额外空间”Morris是加分项值得写。但实际工程里除非内存真的紧张到极致否则用栈版本就够了可读性和健壮性都更好。别为了炫技在生产代码里塞Morris后面维护的人会骂人。7. 常见问题与排查技巧实录7.1 非递归版本死循环排查死循环是非递归中序最常见的bug表现是程序卡住不返回。排查思路按下面这个顺序走现象可能原因排查方法一直循环不结束外层条件写错比如只写了cur ! null检查是否漏了|| !stack.isEmpty()处理完一个节点后卡住忘记cur cur.right检查弹栈后有没有推进cur栈无限增长压栈后忘记cur cur.left检查内层while里有没有推进结果重复右孩子处理逻辑写成了重新压栈确认cur cur.right后是回到外层循环我踩过最坑的一次是内层while写成了while (cur ! null)但里面忘了cur cur.left结果cur一直不变栈一直涨最后OOM。这种错误编译器不会报只能靠走查或者打断点。7.2 结果顺序不对的几种典型情况如果遍历结果不是升序假设是BST大概率是处理节点的时机错了。中序的处理时机是“弹栈之后”如果你在压栈的时候就处理那就变成前序了。如果你在cur cur.right之后处理那顺序也会乱。记住一个口诀压栈不处理弹栈才处理。还有一种情况是结果里少了节点。这通常是因为外层循环提前退出了某些节点还在栈里没弹出来。检查循环条件确保stack.isEmpty()为true时才退出。7.3 空树和单节点的边界处理空树传入root null递归版本第一行就返回了没问题。非递归版本cur null外层循环条件cur ! null || !stack.isEmpty()两个都是false直接跳过循环返回空list也没问题。单节点树压栈、弹栈、处理结果就一个元素同样没问题。真正容易出问题的是只有左孩子的链状树。比如1-2-3-4全在左边根是4。非递归版本会一路压栈压到1然后依次弹出处理结果正确。但如果代码里cur cur.right写成了cur cur.left就会死循环。所以链状树一定要测它是暴露指针推进错误的最佳用例。实操心得写完非递归代码别急着跑满二叉树。先拿一条左链和一条右链各跑一遍这两个用例过了基本逻辑就稳了。满二叉树反而容易掩盖问题因为它的对称性会让某些错误互相抵消。8. 我个人的一些实操体会递归和非递归这两套写法我建议都要练到能默写的程度。不是为了炫技而是因为它们代表了两种不同的思维方式递归是“相信函数会帮你处理好子问题”非递归是“我自己管理状态”。这两种思维在解决其他问题比如快排的非递归实现、图的DFS时都会反复用到。练习的时候有个方法很有效先写递归然后对着递归代码把“函数调用”替换成“压栈”“函数返回”替换成“弹栈”一步步翻译成非递归。翻译的过程中你会自然理解栈里存的到底是什么。这个翻译过程做过两三遍之后非递归代码就不用背了是推出来的。最后再分享一个小技巧如果你在面试中一时想不起非递归怎么写可以先写递归然后跟面试官说“非递归版本我用栈来模拟这个递归过程”接着现场翻译。面试官通常更看重你的思路而不是你背没背过代码。把递归的调用栈画出来翻译成显式栈这个过程本身就是加分项。 
长河君 · 2026/10/14 1:34:24 · 阅读 1.2k Java二叉树中序遍历：递归与非递归实现及Morris优化
1. 为什么中序遍历值得单独拎出来讲二叉树遍历这个事说大不大说小也不小。但凡写过几行数据结构代码的人都能随手写出一个递归版本的中序遍历三行代码搞定闭着眼睛都能默写。但真正到了面试场景、到了实际工程里需要手动控制遍历过程的时候递归那套写法往往就不够用了。我见过太多同学递归写得飞起一让写非递归版本就卡壳要么栈的边界条件搞不清楚要么指针推进的逻辑写反了调半天调不通。这篇文章就围绕Java 二叉树中序遍历这个核心主题把递归和非递归两套方案从头到尾拆一遍。不光是给你代码更重要的是把每一步为什么这么写、栈里面到底存了什么、指针什么时候该动什么时候不该动这些容易含糊的地方讲透。适合正在准备面试的开发者、刚学数据结构的学生以及工作中偶尔需要手写遍历逻辑但不想每次都翻笔记的工程师。读完你至少能做到两件事第一白板上手写非递归中序不出错第二被追问“为什么用栈不用队列”“Morris遍历怎么把空间降到O(1)”的时候能答得上来。中序遍历的特殊性在于它的访问顺序——左、根、右。这个顺序决定了它不像前序遍历那样“遇到节点就能处理”也不像后序遍历那样“处理完子节点再回头处理根”。中序必须先把整条左链走到底才能开始处理第一个节点处理完又要能“回到”父节点继续走它的右子树。这个“回去”的动作就是递归天然帮你做的事也是非递归版本必须用栈手动模拟的核心原因。理解了这一点后面所有的代码都只是这个思路的翻译而已。2. 先把节点定义和测试树定下来2.1 二叉树节点的标准写法在Java里定义一个二叉树节点最朴素的方式就是一个静态内部类三个字段值、左孩子、右孩子。构造方法给一个值的重载就够了左右孩子默认null后续手动挂。public class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int val) { this.val val; } }这里有个小细节值得说一下字段用int还是Integer。如果题目保证节点值都是有效整数用int没问题省去装箱开销。但如果涉及“空节点用null表示”或者值可能为null的场景就得用Integer。我个人的习惯是刷题用int工程里如果节点值可能缺失用Integer更稳妥。另外字段的访问修饰符如果这个类只在当前包内用包级私有不写修饰符就够了如果要跨包老老实实写private加getter/setter或者直接用public图省事——刷题场景下public完全可接受别为了“规范”把代码搞得又臭又长。2.2 构造一棵有代表性的测试树光有节点定义不够得有一棵形状有特点的树来验证遍历结果。我习惯用下面这棵4 / \ 2 6 / \ / \ 1 3 5 7这是一棵满二叉树中序遍历结果是1 2 3 4 5 6 7正好是升序。用升序序列做验证有个好处结果对不对一眼就能看出来不用对着树一个个数。构造代码TreeNode buildTree() { TreeNode n1 new TreeNode(1); TreeNode n3 new TreeNode(3); TreeNode n5 new TreeNode(5); TreeNode n7 new TreeNode(7); TreeNode n2 new TreeNode(2); TreeNode n6 new TreeNode(6); TreeNode n4 new TreeNode(4); n2.left n1; n2.right n3; n6.left n5; n6.right n7; n4.left n2; n4.right n6; return n4; }注意构造顺序建议从叶子往根建先建好所有子节点再挂到父节点上。如果反过来先建根再建子节点容易在挂接的时候引用到还没初始化的变量虽然Java不会报编译错误但逻辑上容易乱。除了这棵满二叉树强烈建议再准备两棵“边界树”来测一棵只有左孩子的链状树比如1-2-3-4全在左边一棵只有右孩子的链状树。链状树是检验非递归代码栈处理是否正确的最佳试金石很多边界bug在满二叉树上跑不出来一上链状树就露馅。3. 递归版本三行代码背后的执行真相3.1 递归代码本身递归版本的中序遍历核心就三行public void inorderRecursive(TreeNode root, ListInteger result) { if (root null) { return; } inorderRecursive(root.left, result); result.add(root.val); inorderRecursive(root.right, result); }调用方式ListInteger result new ArrayList(); inorderRecursive(buildTree(), result); System.out.println(result); // [1, 2, 3, 4, 5, 6, 7]代码简单到没什么好解释的但“简单”恰恰是它容易让人产生错觉的地方。很多人觉得自己懂了递归其实只是记住了这三行的顺序一旦被问“递归调用栈里每一层在干什么”就说不清楚了。3.2 递归调用栈到底发生了什么拿上面那棵树举例从根节点4开始。第一次调用inorder(4)先不处理4直接递归到inorder(2)inorder(2)也不处理2递归到inorder(1)inorder(1)发现左孩子是null于是处理1然后递归右孩子null返回inorder(1)结束。这时候控制权回到inorder(2)处理2再递归inorder(3)处理3返回。控制权回到inorder(4)处理4然后递归右子树同样的逻辑处理5、6、7。整个过程里每个节点被“压栈”的时机是第一次访问到它的时候被“处理”的时机是它的左子树全部处理完之后。这个“压栈”和“处理”之间的时间差就是递归帮你自动保存的上下文。非递归版本要做的就是用显式的栈把这个上下文存起来。实操心得理解递归最好的方式不是盯着代码看而是拿纸画一遍调用栈。每进入一层画一个方框写上当前节点每返回一层划掉一个方框。画完一遍你对“栈里存的是还没处理完的节点”这句话会有完全不同的体感。3.3 递归的隐患栈溢出不是吓唬人递归写法的最大问题不是效率是深度。Java的方法调用栈默认大小跟JVM参数有关一般能撑几千层。如果树退化成一条链比如一万个节点全在左边递归深度就是一万直接StackOverflowError。我实测过在某些默认配置的环境下大概五六千层就开始报错了。所以递归版本适合什么场景树比较平衡、深度可控的场景。比如平衡二叉搜索树深度是log级别的一万个节点也就十几层随便递归。但如果数据来源不可控可能是用户上传的、可能是数据库里读出来的你没法保证它平衡那就得考虑非递归版本或者至少加个深度检查。4. 非递归版本用栈手动模拟递归4.1 核心思路拆解非递归中序的核心思路一句话沿着左链一路压栈压到null为止然后弹栈处理节点再转向右孩子重复这个过程。为什么是“一路压栈”因为中序要求先处理最左边的节点而最左边的节点藏在整条左链的末端。你从根出发不把沿途的节点存起来等处理完最左边那个之后就找不到回去的路了。栈就是用来存这条“回去的路”的。为什么弹栈之后要“转向右孩子”因为弹出来的节点它的左子树已经处理完了不然不会弹到它它自己也处理完了接下来按中序的顺序该处理它的右子树了。右子树可能为空那就继续弹下一个右子树不为空那就对右子树重复“一路压栈”的过程。4.2 完整代码与逐行注释public ListInteger inorderIterative(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 ! null || !stack.isEmpty()两个条件缺一不可。只写cur ! null当cur变成null但栈里还有节点时就提前退出了只写!stack.isEmpty()一开始栈是空的根节点还没压进去就退出了。第二个是cur cur.right之后不能直接处理要回到外层循环重新走“一路压栈”因为右孩子可能还有左子树。4.3 用测试树走一遍完整流程还是那棵树我用表格把每一步的状态列出来这样比纯文字描述清楚得多。步骤cur指向栈内容栈顶在右操作result14[4]4压栈cur2[]22[4, 2]2压栈cur1[]31[4, 2, 1]1压栈curnull[]4null[4, 2]弹1处理1cur1.rightnull[1]5null[4]弹2处理2cur2.right3[1, 2]63[4, 3]3压栈curnull[1, 2]7null[4]弹3处理3curnull[1, 2, 3]8null[]弹4处理4cur4.right6[1, 2, 3, 4]96[6]6压栈cur5[1, 2, 3, 4]105[6, 5]5压栈curnull[1, 2, 3, 4]11null[6]弹5处理5curnull[1, 2, 3, 4, 5]12null[]弹6处理6cur7[1, 2, 3, 4, 5, 6]137[7]7压栈curnull[1, 2, 3, 4, 5, 6]14null[]弹7处理7curnull[1, 2, 3, 4, 5, 6, 7]15null[]循环条件不满足结束[1, 2, 3, 4, 5, 6, 7]走完这一遍栈的作用就非常直观了它保存的是“当前节点处理完之后下一个该处理的节点是谁”。每次弹栈弹出来的就是当前子树里最左下的那个还没处理的节点。4.4 为什么用Deque而不是Stack代码里我用的是DequeTreeNode stack new ArrayDeque()而不是Java自带的Stack类。原因有两个第一Stack是继承自Vector的所有方法都加了synchronized单线程场景下纯属浪费第二Deque接口的push/pop/peek语义更清晰ArrayDeque底层是数组性能比Stack好一截。这是Effective Java里明确推荐的做法实际写代码时养成习惯就好。注意ArrayDeque不允许存null元素。如果你的树节点可能为null并且你想压进去会抛NullPointerException。不过正常逻辑下我们不会把null压栈压栈的都是有效节点所以这个问题一般不会遇到。5. 递归与非递归的对比选型5.1 性能与可读性对照维度递归版本非递归版本代码行数约6行约15行可读性极高一眼看懂中等需要理解栈的作用空间复杂度O(h)h为树高递归栈开销O(h)显式栈开销栈溢出风险树深时存在无堆内存足够大调试难度调用栈深断点跳来跳去状态清晰容易打日志适用场景平衡树、深度可控深度不可控、需要手动控制流程空间复杂度两者都是O(h)但常数不一样。递归的每一层调用栈开销比一个栈帧元素大所以同样深度下非递归更省内存。不过这个差异在大多数场景下可以忽略选型主要看深度是否可控。5.2 什么时候必须用非递归有三种情况我会毫不犹豫选非递归。第一种是树的深度不可控比如从外部数据源构建的树你没法保证它平衡。第二种是需要在遍历过程中做复杂的状态管理比如遍历到某个节点时要暂停、要记录额外信息、要根据条件跳过某些子树这时候显式栈比递归灵活得多。第三种是面试要求很多面试官会直接说“不要用递归”这时候没得选。反过来如果树是平衡的、逻辑简单、追求代码简洁递归版本完全够用没必要为了“显得高级”硬写非递归。我见过有人在一个深度不超过20的配置树上用非递归代码多了一倍维护成本上去了收益为零。工具选型要看场景不是越复杂越好。6. 进阶Morris遍历把空间降到O(1)6.1 Morris遍历的核心思想前面两种方案空间都是O(h)Morris遍历能做到O(1)靠的是一个巧妙的技巧利用叶子节点的空右指针临时指向它的中序后继节点。这样就不需要额外的栈来记录“回去的路”了路就藏在树本身的结构里。具体做法是对于当前节点cur如果它没有左孩子直接处理cur然后curcur.right。如果有左孩子就找到左子树里最右边的节点也就是cur在中序下的前驱如果这个前驱的右指针是null就把它指向cur然后curcur.left如果前驱的右指针已经指向cur了说明左子树已经遍历完了把这个指针恢复成null处理cur然后curcur.right。6.2 Morris中序代码实现public ListInteger inorderMorris(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 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; // 恢复树的原状 result.add(cur.val); cur cur.right; } } } return result; }6.3 Morris遍历的代价与适用性Morris遍历虽然空间是O(1)但它不是没有代价的。第一它在遍历过程中临时修改了树的结构虽然最后会恢复但如果遍历中途抛异常树就被改坏了。第二它的常数时间更大每个节点找前驱的过程要额外走一段路整体时间复杂度虽然还是O(n)但实际跑起来比栈版本慢。第三代码更难写对pre.right ! null pre.right ! cur这个条件少一个都会出问题。我的建议是面试时如果面试官追问“能不能不用额外空间”Morris是加分项值得写。但实际工程里除非内存真的紧张到极致否则用栈版本就够了可读性和健壮性都更好。别为了炫技在生产代码里塞Morris后面维护的人会骂人。7. 常见问题与排查技巧实录7.1 非递归版本死循环排查死循环是非递归中序最常见的bug表现是程序卡住不返回。排查思路按下面这个顺序走现象可能原因排查方法一直循环不结束外层条件写错比如只写了cur ! null检查是否漏了|| !stack.isEmpty()处理完一个节点后卡住忘记cur cur.right检查弹栈后有没有推进cur栈无限增长压栈后忘记cur cur.left检查内层while里有没有推进结果重复右孩子处理逻辑写成了重新压栈确认cur cur.right后是回到外层循环我踩过最坑的一次是内层while写成了while (cur ! null)但里面忘了cur cur.left结果cur一直不变栈一直涨最后OOM。这种错误编译器不会报只能靠走查或者打断点。7.2 结果顺序不对的几种典型情况如果遍历结果不是升序假设是BST大概率是处理节点的时机错了。中序的处理时机是“弹栈之后”如果你在压栈的时候就处理那就变成前序了。如果你在cur cur.right之后处理那顺序也会乱。记住一个口诀压栈不处理弹栈才处理。还有一种情况是结果里少了节点。这通常是因为外层循环提前退出了某些节点还在栈里没弹出来。检查循环条件确保stack.isEmpty()为true时才退出。7.3 空树和单节点的边界处理空树传入root null递归版本第一行就返回了没问题。非递归版本cur null外层循环条件cur ! null || !stack.isEmpty()两个都是false直接跳过循环返回空list也没问题。单节点树压栈、弹栈、处理结果就一个元素同样没问题。真正容易出问题的是只有左孩子的链状树。比如1-2-3-4全在左边根是4。非递归版本会一路压栈压到1然后依次弹出处理结果正确。但如果代码里cur cur.right写成了cur cur.left就会死循环。所以链状树一定要测它是暴露指针推进错误的最佳用例。实操心得写完非递归代码别急着跑满二叉树。先拿一条左链和一条右链各跑一遍这两个用例过了基本逻辑就稳了。满二叉树反而容易掩盖问题因为它的对称性会让某些错误互相抵消。8. 我个人的一些实操体会递归和非递归这两套写法我建议都要练到能默写的程度。不是为了炫技而是因为它们代表了两种不同的思维方式递归是“相信函数会帮你处理好子问题”非递归是“我自己管理状态”。这两种思维在解决其他问题比如快排的非递归实现、图的DFS时都会反复用到。练习的时候有个方法很有效先写递归然后对着递归代码把“函数调用”替换成“压栈”“函数返回”替换成“弹栈”一步步翻译成非递归。翻译的过程中你会自然理解栈里存的到底是什么。这个翻译过程做过两三遍之后非递归代码就不用背了是推出来的。最后再分享一个小技巧如果你在面试中一时想不起非递归怎么写可以先写递归然后跟面试官说“非递归版本我用栈来模拟这个递归过程”接着现场翻译。面试官通常更看重你的思路而不是你背没背过代码。把递归的调用栈画出来翻译成显式栈这个过程本身就是加分项。