很多人问我二叉树的三种遍历到底怎么理解才透彻。说实话这类问题在网上随便一搜就是一大把教程但大多只是把递归代码贴出来再配一张三种遍历访问顺序的表格。看得多了你会发现一个尴尬的局面代码背得滚瓜烂熟表格也记住了“前序根左右、中序左根右、后序左右根”可一旦碰到几道变体题比如让你写个非递归的后序遍历或者让你用遍历序列重建二叉树立刻卡壳。这篇文章我打算换个讲法不急着堆代码先带着你把三种遍历的本质逻辑过一遍再把“为什么代码要那么写”“为什么后序的非递归那么别扭”这些藏在角落里的东西挖出来。内容面向刚学完树结构、准备笔试面试或者想彻底打通这块知识点的读者我尽量做到既有直观逻辑也能直接上手写。1. 三种遍历的分工逻辑根的位置就是一切1.1 别背“根左右”先搞懂“访问时机”这个概念先看最基本的一张图景。二叉树遍历的核心动作就两个走到某个节点然后决定先处理这个节点本身、还是先钻进它的左子树、还是先钻进它的右子树。所谓的“序”本质上是“根节点被处理的那个时间点”。前序遍历先处理当前节点再处理左子树最后处理右子树。也就是“根”最早登场。中序遍历先处理左子树再处理当前节点最后处理右子树。“根”夹在中间。后序遍历先处理左子树再处理右子树最后才轮到当前节点。“根”压轴出场。很多人默认这只是在描述输出顺序不够。它更关键的作用是定义了递归函数里那行“访问操作”写在哪。如果你写的是递归实现三种遍历的代码框架完全一致唯一不同的就是输出语句在调用左子树和调用右子树之间的位置。就这一行的位置移动决定了整棵树被输出的顺序。我习惯用一个生活中的比喻来解释把节点当成一个文件夹左子树和右子树是它里面的两个子文件夹而“访问”这个动作可以理解成给文件夹贴标签。前序是“进门先贴标签再去翻左边的子文件夹再翻右边的”中序是“先去翻完左边的子文件夹回来贴当前标签再翻右边的”后序是“先把两个子文件夹翻个底朝天回来才贴这个文件夹的标签”。很直观对吗1.2 三种遍历的递归代码差的就是那一个位置用一个极简的二叉树节点类来说Java写法大概长这样class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val x; } }三种遍历的递归代码放一起对比你一眼就能看到差别// 前序遍历 void preOrder(TreeNode root) { if (root null) return; System.out.print(root.val ); // 访问根 preOrder(root.left); // 左子树 preOrder(root.right); // 右子树 } // 中序遍历 void inOrder(TreeNode root) { if (root null) return; inOrder(root.left); // 左子树 System.out.print(root.val ); // 访问根 inOrder(root.right); // 右子树 } // 后序遍历 void postOrder(TreeNode root) { if (root null) return; postOrder(root.left); // 左子树 postOrder(root.right); // 右子树 System.out.print(root.val ); // 访问根 }三份代码长得几乎一样唯一变的就是那行打印语句的位置。这也解释了为什么初学者经常写着写着就混了——因为框架确实太像了。可一旦你抓住“访问时机”这个视角就再也不会乱。面试的时候如果紧张在纸上先画一个只有三个节点的最小树一个根、一个左孩子、一个右孩子。然后问自己我现在要先看谁自然就能写出正确的顺序。不过递归代码好写归好写它隐藏了一个非常容易忽略的细节递归的顺序不是靠“记忆”出来的而是靠系统调用栈一层层压进去、再一层层弹出来实现的。这个机制如果不理解后面看非递归遍历会非常痛苦。2. 递归的顺序是怎么被函数调用栈“安排”出来的2.1 一步一步手动模拟一棵小树用栈理解中序的轨迹我给你一棵具体的小树节点值分别是1、2、3、4、5、6、7结构是1 / \ 2 3 / \ \ 4 5 6 \ 7对这不是一棵满二叉树故意留了点不规则结构方便观察。现在手动走一遍中序遍历的递归过程边走边看调用栈的变化从根节点1进入inOrder(1)压栈。inOrder(1)先调用左子树inOrder(2)压栈。进入inOrder(2)又先调用它的左子树inOrder(4)压栈。inOrder(4)的左孩子是null直接返回。此时inOrder(4)还没打印任何东西接着执行打印输出“4”。然后调用4的右孩子也是null返回。inOrder(4)执行完毕出栈。回到inOrder(2)刚才卡在调用左子树那一步现在左子树整体返回了接着打印“2”。调用2的右子树inOrder(5)压栈。5有左孩子null跳过打印“5”5的右孩子是7继续inOrder(7)压栈。7左孩子null打印“7”右孩子null返回7出栈。5处理完出栈回到22也处理完出栈回到1的调用。此时打印“1”然后再进入右子树按相同逻辑输出3、6。最终中序输出4 2 7 5 1 3 6。这个过程我想要你记住一件事每个递归函数在执行时并不是“一口气”跑完的它会卡在调用左子树的那个位置等左子树整棵返回之后才继续。这个“卡住”的动作就是系统栈把它压在那里的原因。理解了这个再看非递归实现思路立刻就清楚了——我们要做的就是用自己管理的栈模拟这种“卡住再回来”的过程。2.2 前序和后序的递归轨迹差别前序是最符合人类直觉的进去就打印所以它的轨迹基本就是“走到哪打印到哪”系统栈的深度决定了路径的深度。后序则相反一个节点要等左右两棵子树全部返回才能打印这意味着在系统栈里这个节点的“活着时间”是所有遍历中最久的。这也是为什么后序遍历在工程上经常被用来做树的销毁或内存释放——你必须先处理完孩子才能释放父节点否则孩子就丢了。顺带一提很多树的题目里凡是涉及“从底向上汇总”的逻辑比如判断平衡二叉树、计算树的高度基本都是后序的骨架因为需要先拿到左右子树的结果才能算当前节点。3. 非递归实现真正检验你懂不懂“栈”的时候3.1 前序非递归唯一一个简单到不需要思考的前序非递归用栈模拟思路很顺根先入栈然后循环弹出一个节点打印再把右孩子压入栈再压左孩子。为什么要先压右再压左因为栈是后进先出先压右边左边后压下一次弹出来的就是左孩子如此才能保证“根-左-右”的访问顺序。void preOrderIter(TreeNode root) { if (root null) return; DequeTreeNode stack new ArrayDeque(); stack.push(root); while (!stack.isEmpty()) { TreeNode node stack.pop(); System.out.print(node.val ); if (node.right ! null) stack.push(node.right); if (node.left ! null) stack.push(node.left); } }这里我用了ArrayDeque而不是Stack。Stack是Java里一个遗留类性能一般而且继承了Vector方法带锁工程上不推荐。ArrayDeque做栈用足够面试这么写也完全没问题。3.2 中序非递归核心是“一路向左弹一个进右子树”中序非递归是我觉得最值得手推一遍的实现。它的核心逻辑就一句话先把当前节点的所有左孩子压入栈然后弹出一个节点打印它再把当前指针移到右孩子重复这个循环。void inOrderIter(TreeNode root) { DequeTreeNode stack new ArrayDeque(); TreeNode cur root; while (cur ! null || !stack.isEmpty()) { while (cur ! null) { stack.push(cur); cur cur.left; } cur stack.pop(); System.out.print(cur.val ); cur cur.right; } }为什么中序非递归不用像前序那样先处理根因为中序的“根”要等左子树完全结束才可以打印。所以一开始不能打印当前节点得先把当前的根压栈然后一路钻到最左边。等左边到头了弹出一个节点这时它的左子树已经全部处理完恰好可以打印然后指针转向右子树右子树又重复同样的过程。这个代码建议你自己写一遍然后扔几组数据跑一跑尤其试一下那种只有右链的退化树比如1-2-3-4这种斜树。你会发现外层的while (cur ! null || !stack.isEmpty())两个条件缺一不可cur ! null处理的是“还能继续向左深入”的情况!stack.isEmpty()处理的是“当前没路可走了但栈里还有等着被打印的祖先”的情况。3.3 后序非递归为什么直接模拟那么别扭到了最让人头疼的后序。你可能会想前序我用“根-右-左”的顺序压栈然后倒序输出不就得到后序了吗确实有一个非常巧的间接方法代码极短void postOrderIterReverse(TreeNode root) { DequeTreeNode stack new ArrayDeque(); DequeInteger output new ArrayDeque(); if (root ! null) stack.push(root); while (!stack.isEmpty()) { TreeNode node stack.pop(); output.push(node.val); if (node.left ! null) stack.push(node.left); if (node.right ! null) stack.push(node.right); } while (!output.isEmpty()) { System.out.print(output.pop() ); } }这个技巧的原理值得说一下前序是“中-左-右”如果我们把左右压栈顺序反过来就变成“中-右-左”的访问顺序再把结果整个逆序得到的恰好是后序的“左-右-中”。我挺喜欢这个方法因为它很少出错面试时如果时间紧先写这个版本也能过关。不过如果面试官要求你“别用两个栈就一个栈硬写后序”那才是真正考验理解的地方。为什么难因为后序非递归无法区分当前节点是第一次被弹出还是第二次被弹出。前序和中序弹出即打印一次搞定后序要求先处理左右子树左右子树处理完还得回到父节点再打印而回到父节点意味着父节点会被弹出两次第一次弹出是左右子树还没处理完需要再压回去第二次弹出才是真打印。所以单栈后序必须引入一个辅助变量记录“上一次处理的节点”用来判断右子树是否已经处理完。void postOrderIterOneStack(TreeNode root) { DequeTreeNode stack new ArrayDeque(); TreeNode cur root; TreeNode lastVisited null; while (cur ! null || !stack.isEmpty()) { if (cur ! null) { stack.push(cur); cur cur.left; } else { TreeNode peek stack.peek(); if (peek.right ! null lastVisited ! peek.right) { cur peek.right; } else { System.out.print(peek.val ); lastVisited stack.pop(); } } } }这个版本的判断逻辑要仔细想如果当前节点的右子树存在而且上一次处理的不是它的右孩子说明右子树还没被处理那就先把右子树放进去否则右子树要么不存在要么已经处理完了这时左子树也早处理完了可以打印当前节点了。用lastVisited记录上一次弹出的节点是最常用的单栈后序写法。4. 再说一个进阶技巧Morris遍历如何做到O(1)空间4.1 用线索化代替栈核心是找出“前驱节点”递归和非递归两种实现空间复杂度都是O(h)其中h是树的高度。最坏情况树退化成链h等于n栈的消耗就是O(n)。面试官要是追问“能不能把空间省到O(1)”那你得知道Morris遍历。Morris的思路不走寻常路它不用栈而是利用树里大量空闲的右指针原本指向null的那些节点来临时创建线索完成遍历后再把线索恢复成null。以中序Morris为例核心逻辑是寻找当前节点左子树中“最右的那个节点”这个节点在中序遍历的顺序里就是当前节点的前驱。如果这个最右节点的右指针是空的就把它指向当前节点建立线索如果它的右指针已经指向当前节点说明左子树已经遍历完了赶紧把指针恢复成null防止树的结构被永久改写。void morrisInOrder(TreeNode root) { TreeNode cur root; while (cur ! null) { if (cur.left null) { System.out.print(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; System.out.print(cur.val ); cur cur.right; } } } }4.2 什么时候值得用Morris什么时候别用要我说Morris属于那种“面试知道原理可以加分但工程上多数时候没必要”的写法。因为它会临时修改树结构虽然最终会恢复原状但如果在多线程环境下同时遍历一棵树或者有一个线程正在读这棵树线索化过程中的临时改动就可能引发奇怪的问题。还有一点要注意Morris遍历改写了节点的右指针对于只读场景没问题但如果你的二叉树本身有额外语义比如节点右指针被用来存其他信息用了Morris就可能把业务数据破坏掉。所以我的建议是应付面试至少理解前序、中序的Morris写法后序Morris不要求硬背真正工程里绝大多数场景用递归或者普通非递归就够了性能瓶颈一般也不会卡在遍历上。5. 由两种遍历序列反推二叉树前序中序的重建5.1 为什么前序中序能唯一重建而后序前序不能遍历序列在面试题里还有一个经典变体给了前序和中序让你重建二叉树。这个题能成立的前提是前序提供“根是谁”的信息中序提供“左右子树的分界线在哪”。两者互补恰好能唯一还原结构。反过来只有前序和后序是还原不了唯一二叉树的。举个例子两个节点的情况前序是1 2后序是2 1这棵树既可以是1的左孩子是2也可以是1的右孩子是2两种结构输出序列完全一样。这里面的本质原因在于前序和后序都只能告诉你根是谁但无法区分左右子树的位置关系。所以碰到“用前序和后序重建二叉树”的题目时常规判断是信息不足除非题目额外规定了必须是满二叉树。5.2 递归重建的切分套路重建采用递归切分的思路。以LeetCode 105为例给定前序数组preorder和中序数组inorder步骤如下前序数组的第一个元素就是整棵树的根。在中序数组中找到这个根的位置indexindex左边的全部属于左子树右边全部属于右子树。根据左子树的节点个数去前序数组中切分出对应的左子树前序段和右子树前序段。递归重建左右子树。Java递归写法大概长这样TreeNode buildTree(int[] preorder, int[] inorder) { MapInteger, Integer map new HashMap(); for (int i 0; i inorder.length; i) { map.put(inorder[i], i); } return build(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1, map); } TreeNode build(int[] preorder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd, MapInteger, Integer map) { if (preStart preEnd || inStart inEnd) return null; int rootVal preorder[preStart]; TreeNode root new TreeNode(rootVal); int rootIndexInInorder map.get(rootVal); int leftSize rootIndexInInorder - inStart; root.left build(preorder, preStart 1, preStart leftSize, inorder, inStart, rootIndexInInorder - 1, map); root.right build(preorder, preStart leftSize 1, preEnd, inorder, rootIndexInInorder 1, inEnd, map); return root; }这里用哈希表提前存中序数组每个值对应的下标是为了让查找根的位置从O(n)降到O(1)。分割的关键在于leftSize的计算中序数组里根左边的元素个数就是左子树的规模这个规模直接影响前序数组怎么切。如果是中序后序重建思路完全对称唯一的区别是后序数组的最后一个元素是根然后从后往前切。建议你写完前序中序之后把后序中序也当作练习自己推一遍。别直接背答案动手画出两棵不同的树分别写出序列再手动执行一遍切分逻辑这一关才算真正过了。6. 三种遍历在真实场景里的分工从表达式计算到文件系统6.1 编译器里的表达式树为什么用后序数据结构这门课总觉得抽象其实遍历在真实系统里到处都是。最典型的是表达式树。比如(a b) * (c - d)可以用二叉树表示乘法是根左子树是加法右子树是减法。如果你做后序遍历输出的序列恰好就是后缀表达式a b c d - *也就是计算机最容易用栈直接求值的形式。这也是为什么很多计算器、编译器的表达式求值模块会把表达式树转成后缀表达式来分析。反过来说中序遍历一个表达式树会得到a b * c - d这样的中缀表达式但这里有个坑中序遍历输出的中缀表达式不一定带括号所以可能出现运算符优先级问题。工程上如果真要打印中缀还需要根据节点层级补括号不能单纯依赖遍历顺序。6.2 文件系统目录深度统计的天然后序再看文件系统。一个目录可以被看作节点子目录和文件是它的子树。如果你想统计某个目录下所有文件的总大小必须先把每个子目录的大小统计出来再逐级向上汇总。这个模式天然就是后序遍历先处理左右子树再回到根节点累加结果。递归删除目录也是一样必须先把目录里的所有内容清空才能删掉目录本身后序的“先孩子后父母”完美匹配这个操作顺序。前序也有它的用武之地。比如很多不要深究细节的“快速预览”场景先输出根节点做点简单的展示再继续深入子节点这种前序的“即时反馈”特性在UI渲染上很有优势。还有一个场景是序列化和反序列化二叉树用前序遍历加空指针标记比如用#表示null可以唯一确定一棵树这也是很多序列化方案的基础逻辑因为前序“根在前”的描述顺序最方便反序列化时一个节点一个节点重建。6.3 做选择前先想清楚需求所以三种遍历没有绝对的谁优谁劣关键看你要什么。想要“先看到当前节点再深入细节”选前序想要“按自然顺序输出有序数据”比如二叉搜索树中序就是从小到大选中序想要“先处理完所有子树再汇总到根”选后序。理解了每种遍历对应的“时机”做题和实际开发时都不用再纠结。7. 绕过几个常见的“陷阱”写遍历代码最容易犯的错7.1 非递归写错时先检查是不是指针更新漏了中序非递归最容易犯的错是漏写cur cur.right;。如果少了这一行当左子树和根都处理完之后程序永远不会进入右子树会陷入死循环或者提前退出。调试时看到这种情况第一反应就检查当前指针有没有在打印后正确指向右孩子。后序单栈写法最容易犯的错是lastVisited的更新时机。一定要在弹出节点并打印之后立刻赋值而不是在peek的时候就赋值。很多人在循环里把lastVisited提前更新了结果判断lastVisited ! peek.right的时候拿到的仍然是旧值整个遍历顺序就会乱掉。7.2 递归层数深到爆栈怎么办如果二叉树非常不平衡比如10万个节点全挂在单侧递归遍历必然爆栈。这时候要么用非递归实现手动管理栈要么把系统栈调大比如JVM加-Xss参数。工程上处理海量数据时我更倾向于一开始就写非递归版本毕竟健壮性优先同时非递归的调试难度其实并没有比递归高多少。7.3 同一棵树的遍历结果不代表“唯一顺序”还有一个容易晕的点如果你在纸上手算遍历序列最好每次都用同一棵树画两遍一遍用“递归展开”的视角一遍用“栈模拟”的视角。我自己当年做过一个对比同时用两种视角走同一棵树写着写着就会发现栈模拟其实是递归展开的“底片”两者的轨迹完全重叠。一旦建立了这个对应关系后面看任何遍历代码都不觉得玄乎了。我在实际面试别人的时候发现能把单栈后序遍历写出来的人基本上对栈的理解已经过关了。所以如果你想检验自己到底懂没懂非递归遍历别只看前序和中序直接挑战后序。写不出来也不要紧照着前面那个单栈版本自己手动走一棵树把每个节点的压栈、出栈、打印时机全部记下来走完这一遍你就再也不会怕遍历了。 
长河君 · 2026/10/14 1:26:22 · 阅读 1.2k 二叉树遍历全解析：递归、非递归与Morris遍历
很多人问我二叉树的三种遍历到底怎么理解才透彻。说实话这类问题在网上随便一搜就是一大把教程但大多只是把递归代码贴出来再配一张三种遍历访问顺序的表格。看得多了你会发现一个尴尬的局面代码背得滚瓜烂熟表格也记住了“前序根左右、中序左根右、后序左右根”可一旦碰到几道变体题比如让你写个非递归的后序遍历或者让你用遍历序列重建二叉树立刻卡壳。这篇文章我打算换个讲法不急着堆代码先带着你把三种遍历的本质逻辑过一遍再把“为什么代码要那么写”“为什么后序的非递归那么别扭”这些藏在角落里的东西挖出来。内容面向刚学完树结构、准备笔试面试或者想彻底打通这块知识点的读者我尽量做到既有直观逻辑也能直接上手写。1. 三种遍历的分工逻辑根的位置就是一切1.1 别背“根左右”先搞懂“访问时机”这个概念先看最基本的一张图景。二叉树遍历的核心动作就两个走到某个节点然后决定先处理这个节点本身、还是先钻进它的左子树、还是先钻进它的右子树。所谓的“序”本质上是“根节点被处理的那个时间点”。前序遍历先处理当前节点再处理左子树最后处理右子树。也就是“根”最早登场。中序遍历先处理左子树再处理当前节点最后处理右子树。“根”夹在中间。后序遍历先处理左子树再处理右子树最后才轮到当前节点。“根”压轴出场。很多人默认这只是在描述输出顺序不够。它更关键的作用是定义了递归函数里那行“访问操作”写在哪。如果你写的是递归实现三种遍历的代码框架完全一致唯一不同的就是输出语句在调用左子树和调用右子树之间的位置。就这一行的位置移动决定了整棵树被输出的顺序。我习惯用一个生活中的比喻来解释把节点当成一个文件夹左子树和右子树是它里面的两个子文件夹而“访问”这个动作可以理解成给文件夹贴标签。前序是“进门先贴标签再去翻左边的子文件夹再翻右边的”中序是“先去翻完左边的子文件夹回来贴当前标签再翻右边的”后序是“先把两个子文件夹翻个底朝天回来才贴这个文件夹的标签”。很直观对吗1.2 三种遍历的递归代码差的就是那一个位置用一个极简的二叉树节点类来说Java写法大概长这样class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val x; } }三种遍历的递归代码放一起对比你一眼就能看到差别// 前序遍历 void preOrder(TreeNode root) { if (root null) return; System.out.print(root.val ); // 访问根 preOrder(root.left); // 左子树 preOrder(root.right); // 右子树 } // 中序遍历 void inOrder(TreeNode root) { if (root null) return; inOrder(root.left); // 左子树 System.out.print(root.val ); // 访问根 inOrder(root.right); // 右子树 } // 后序遍历 void postOrder(TreeNode root) { if (root null) return; postOrder(root.left); // 左子树 postOrder(root.right); // 右子树 System.out.print(root.val ); // 访问根 }三份代码长得几乎一样唯一变的就是那行打印语句的位置。这也解释了为什么初学者经常写着写着就混了——因为框架确实太像了。可一旦你抓住“访问时机”这个视角就再也不会乱。面试的时候如果紧张在纸上先画一个只有三个节点的最小树一个根、一个左孩子、一个右孩子。然后问自己我现在要先看谁自然就能写出正确的顺序。不过递归代码好写归好写它隐藏了一个非常容易忽略的细节递归的顺序不是靠“记忆”出来的而是靠系统调用栈一层层压进去、再一层层弹出来实现的。这个机制如果不理解后面看非递归遍历会非常痛苦。2. 递归的顺序是怎么被函数调用栈“安排”出来的2.1 一步一步手动模拟一棵小树用栈理解中序的轨迹我给你一棵具体的小树节点值分别是1、2、3、4、5、6、7结构是1 / \ 2 3 / \ \ 4 5 6 \ 7对这不是一棵满二叉树故意留了点不规则结构方便观察。现在手动走一遍中序遍历的递归过程边走边看调用栈的变化从根节点1进入inOrder(1)压栈。inOrder(1)先调用左子树inOrder(2)压栈。进入inOrder(2)又先调用它的左子树inOrder(4)压栈。inOrder(4)的左孩子是null直接返回。此时inOrder(4)还没打印任何东西接着执行打印输出“4”。然后调用4的右孩子也是null返回。inOrder(4)执行完毕出栈。回到inOrder(2)刚才卡在调用左子树那一步现在左子树整体返回了接着打印“2”。调用2的右子树inOrder(5)压栈。5有左孩子null跳过打印“5”5的右孩子是7继续inOrder(7)压栈。7左孩子null打印“7”右孩子null返回7出栈。5处理完出栈回到22也处理完出栈回到1的调用。此时打印“1”然后再进入右子树按相同逻辑输出3、6。最终中序输出4 2 7 5 1 3 6。这个过程我想要你记住一件事每个递归函数在执行时并不是“一口气”跑完的它会卡在调用左子树的那个位置等左子树整棵返回之后才继续。这个“卡住”的动作就是系统栈把它压在那里的原因。理解了这个再看非递归实现思路立刻就清楚了——我们要做的就是用自己管理的栈模拟这种“卡住再回来”的过程。2.2 前序和后序的递归轨迹差别前序是最符合人类直觉的进去就打印所以它的轨迹基本就是“走到哪打印到哪”系统栈的深度决定了路径的深度。后序则相反一个节点要等左右两棵子树全部返回才能打印这意味着在系统栈里这个节点的“活着时间”是所有遍历中最久的。这也是为什么后序遍历在工程上经常被用来做树的销毁或内存释放——你必须先处理完孩子才能释放父节点否则孩子就丢了。顺带一提很多树的题目里凡是涉及“从底向上汇总”的逻辑比如判断平衡二叉树、计算树的高度基本都是后序的骨架因为需要先拿到左右子树的结果才能算当前节点。3. 非递归实现真正检验你懂不懂“栈”的时候3.1 前序非递归唯一一个简单到不需要思考的前序非递归用栈模拟思路很顺根先入栈然后循环弹出一个节点打印再把右孩子压入栈再压左孩子。为什么要先压右再压左因为栈是后进先出先压右边左边后压下一次弹出来的就是左孩子如此才能保证“根-左-右”的访问顺序。void preOrderIter(TreeNode root) { if (root null) return; DequeTreeNode stack new ArrayDeque(); stack.push(root); while (!stack.isEmpty()) { TreeNode node stack.pop(); System.out.print(node.val ); if (node.right ! null) stack.push(node.right); if (node.left ! null) stack.push(node.left); } }这里我用了ArrayDeque而不是Stack。Stack是Java里一个遗留类性能一般而且继承了Vector方法带锁工程上不推荐。ArrayDeque做栈用足够面试这么写也完全没问题。3.2 中序非递归核心是“一路向左弹一个进右子树”中序非递归是我觉得最值得手推一遍的实现。它的核心逻辑就一句话先把当前节点的所有左孩子压入栈然后弹出一个节点打印它再把当前指针移到右孩子重复这个循环。void inOrderIter(TreeNode root) { DequeTreeNode stack new ArrayDeque(); TreeNode cur root; while (cur ! null || !stack.isEmpty()) { while (cur ! null) { stack.push(cur); cur cur.left; } cur stack.pop(); System.out.print(cur.val ); cur cur.right; } }为什么中序非递归不用像前序那样先处理根因为中序的“根”要等左子树完全结束才可以打印。所以一开始不能打印当前节点得先把当前的根压栈然后一路钻到最左边。等左边到头了弹出一个节点这时它的左子树已经全部处理完恰好可以打印然后指针转向右子树右子树又重复同样的过程。这个代码建议你自己写一遍然后扔几组数据跑一跑尤其试一下那种只有右链的退化树比如1-2-3-4这种斜树。你会发现外层的while (cur ! null || !stack.isEmpty())两个条件缺一不可cur ! null处理的是“还能继续向左深入”的情况!stack.isEmpty()处理的是“当前没路可走了但栈里还有等着被打印的祖先”的情况。3.3 后序非递归为什么直接模拟那么别扭到了最让人头疼的后序。你可能会想前序我用“根-右-左”的顺序压栈然后倒序输出不就得到后序了吗确实有一个非常巧的间接方法代码极短void postOrderIterReverse(TreeNode root) { DequeTreeNode stack new ArrayDeque(); DequeInteger output new ArrayDeque(); if (root ! null) stack.push(root); while (!stack.isEmpty()) { TreeNode node stack.pop(); output.push(node.val); if (node.left ! null) stack.push(node.left); if (node.right ! null) stack.push(node.right); } while (!output.isEmpty()) { System.out.print(output.pop() ); } }这个技巧的原理值得说一下前序是“中-左-右”如果我们把左右压栈顺序反过来就变成“中-右-左”的访问顺序再把结果整个逆序得到的恰好是后序的“左-右-中”。我挺喜欢这个方法因为它很少出错面试时如果时间紧先写这个版本也能过关。不过如果面试官要求你“别用两个栈就一个栈硬写后序”那才是真正考验理解的地方。为什么难因为后序非递归无法区分当前节点是第一次被弹出还是第二次被弹出。前序和中序弹出即打印一次搞定后序要求先处理左右子树左右子树处理完还得回到父节点再打印而回到父节点意味着父节点会被弹出两次第一次弹出是左右子树还没处理完需要再压回去第二次弹出才是真打印。所以单栈后序必须引入一个辅助变量记录“上一次处理的节点”用来判断右子树是否已经处理完。void postOrderIterOneStack(TreeNode root) { DequeTreeNode stack new ArrayDeque(); TreeNode cur root; TreeNode lastVisited null; while (cur ! null || !stack.isEmpty()) { if (cur ! null) { stack.push(cur); cur cur.left; } else { TreeNode peek stack.peek(); if (peek.right ! null lastVisited ! peek.right) { cur peek.right; } else { System.out.print(peek.val ); lastVisited stack.pop(); } } } }这个版本的判断逻辑要仔细想如果当前节点的右子树存在而且上一次处理的不是它的右孩子说明右子树还没被处理那就先把右子树放进去否则右子树要么不存在要么已经处理完了这时左子树也早处理完了可以打印当前节点了。用lastVisited记录上一次弹出的节点是最常用的单栈后序写法。4. 再说一个进阶技巧Morris遍历如何做到O(1)空间4.1 用线索化代替栈核心是找出“前驱节点”递归和非递归两种实现空间复杂度都是O(h)其中h是树的高度。最坏情况树退化成链h等于n栈的消耗就是O(n)。面试官要是追问“能不能把空间省到O(1)”那你得知道Morris遍历。Morris的思路不走寻常路它不用栈而是利用树里大量空闲的右指针原本指向null的那些节点来临时创建线索完成遍历后再把线索恢复成null。以中序Morris为例核心逻辑是寻找当前节点左子树中“最右的那个节点”这个节点在中序遍历的顺序里就是当前节点的前驱。如果这个最右节点的右指针是空的就把它指向当前节点建立线索如果它的右指针已经指向当前节点说明左子树已经遍历完了赶紧把指针恢复成null防止树的结构被永久改写。void morrisInOrder(TreeNode root) { TreeNode cur root; while (cur ! null) { if (cur.left null) { System.out.print(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; System.out.print(cur.val ); cur cur.right; } } } }4.2 什么时候值得用Morris什么时候别用要我说Morris属于那种“面试知道原理可以加分但工程上多数时候没必要”的写法。因为它会临时修改树结构虽然最终会恢复原状但如果在多线程环境下同时遍历一棵树或者有一个线程正在读这棵树线索化过程中的临时改动就可能引发奇怪的问题。还有一点要注意Morris遍历改写了节点的右指针对于只读场景没问题但如果你的二叉树本身有额外语义比如节点右指针被用来存其他信息用了Morris就可能把业务数据破坏掉。所以我的建议是应付面试至少理解前序、中序的Morris写法后序Morris不要求硬背真正工程里绝大多数场景用递归或者普通非递归就够了性能瓶颈一般也不会卡在遍历上。5. 由两种遍历序列反推二叉树前序中序的重建5.1 为什么前序中序能唯一重建而后序前序不能遍历序列在面试题里还有一个经典变体给了前序和中序让你重建二叉树。这个题能成立的前提是前序提供“根是谁”的信息中序提供“左右子树的分界线在哪”。两者互补恰好能唯一还原结构。反过来只有前序和后序是还原不了唯一二叉树的。举个例子两个节点的情况前序是1 2后序是2 1这棵树既可以是1的左孩子是2也可以是1的右孩子是2两种结构输出序列完全一样。这里面的本质原因在于前序和后序都只能告诉你根是谁但无法区分左右子树的位置关系。所以碰到“用前序和后序重建二叉树”的题目时常规判断是信息不足除非题目额外规定了必须是满二叉树。5.2 递归重建的切分套路重建采用递归切分的思路。以LeetCode 105为例给定前序数组preorder和中序数组inorder步骤如下前序数组的第一个元素就是整棵树的根。在中序数组中找到这个根的位置indexindex左边的全部属于左子树右边全部属于右子树。根据左子树的节点个数去前序数组中切分出对应的左子树前序段和右子树前序段。递归重建左右子树。Java递归写法大概长这样TreeNode buildTree(int[] preorder, int[] inorder) { MapInteger, Integer map new HashMap(); for (int i 0; i inorder.length; i) { map.put(inorder[i], i); } return build(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1, map); } TreeNode build(int[] preorder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd, MapInteger, Integer map) { if (preStart preEnd || inStart inEnd) return null; int rootVal preorder[preStart]; TreeNode root new TreeNode(rootVal); int rootIndexInInorder map.get(rootVal); int leftSize rootIndexInInorder - inStart; root.left build(preorder, preStart 1, preStart leftSize, inorder, inStart, rootIndexInInorder - 1, map); root.right build(preorder, preStart leftSize 1, preEnd, inorder, rootIndexInInorder 1, inEnd, map); return root; }这里用哈希表提前存中序数组每个值对应的下标是为了让查找根的位置从O(n)降到O(1)。分割的关键在于leftSize的计算中序数组里根左边的元素个数就是左子树的规模这个规模直接影响前序数组怎么切。如果是中序后序重建思路完全对称唯一的区别是后序数组的最后一个元素是根然后从后往前切。建议你写完前序中序之后把后序中序也当作练习自己推一遍。别直接背答案动手画出两棵不同的树分别写出序列再手动执行一遍切分逻辑这一关才算真正过了。6. 三种遍历在真实场景里的分工从表达式计算到文件系统6.1 编译器里的表达式树为什么用后序数据结构这门课总觉得抽象其实遍历在真实系统里到处都是。最典型的是表达式树。比如(a b) * (c - d)可以用二叉树表示乘法是根左子树是加法右子树是减法。如果你做后序遍历输出的序列恰好就是后缀表达式a b c d - *也就是计算机最容易用栈直接求值的形式。这也是为什么很多计算器、编译器的表达式求值模块会把表达式树转成后缀表达式来分析。反过来说中序遍历一个表达式树会得到a b * c - d这样的中缀表达式但这里有个坑中序遍历输出的中缀表达式不一定带括号所以可能出现运算符优先级问题。工程上如果真要打印中缀还需要根据节点层级补括号不能单纯依赖遍历顺序。6.2 文件系统目录深度统计的天然后序再看文件系统。一个目录可以被看作节点子目录和文件是它的子树。如果你想统计某个目录下所有文件的总大小必须先把每个子目录的大小统计出来再逐级向上汇总。这个模式天然就是后序遍历先处理左右子树再回到根节点累加结果。递归删除目录也是一样必须先把目录里的所有内容清空才能删掉目录本身后序的“先孩子后父母”完美匹配这个操作顺序。前序也有它的用武之地。比如很多不要深究细节的“快速预览”场景先输出根节点做点简单的展示再继续深入子节点这种前序的“即时反馈”特性在UI渲染上很有优势。还有一个场景是序列化和反序列化二叉树用前序遍历加空指针标记比如用#表示null可以唯一确定一棵树这也是很多序列化方案的基础逻辑因为前序“根在前”的描述顺序最方便反序列化时一个节点一个节点重建。6.3 做选择前先想清楚需求所以三种遍历没有绝对的谁优谁劣关键看你要什么。想要“先看到当前节点再深入细节”选前序想要“按自然顺序输出有序数据”比如二叉搜索树中序就是从小到大选中序想要“先处理完所有子树再汇总到根”选后序。理解了每种遍历对应的“时机”做题和实际开发时都不用再纠结。7. 绕过几个常见的“陷阱”写遍历代码最容易犯的错7.1 非递归写错时先检查是不是指针更新漏了中序非递归最容易犯的错是漏写cur cur.right;。如果少了这一行当左子树和根都处理完之后程序永远不会进入右子树会陷入死循环或者提前退出。调试时看到这种情况第一反应就检查当前指针有没有在打印后正确指向右孩子。后序单栈写法最容易犯的错是lastVisited的更新时机。一定要在弹出节点并打印之后立刻赋值而不是在peek的时候就赋值。很多人在循环里把lastVisited提前更新了结果判断lastVisited ! peek.right的时候拿到的仍然是旧值整个遍历顺序就会乱掉。7.2 递归层数深到爆栈怎么办如果二叉树非常不平衡比如10万个节点全挂在单侧递归遍历必然爆栈。这时候要么用非递归实现手动管理栈要么把系统栈调大比如JVM加-Xss参数。工程上处理海量数据时我更倾向于一开始就写非递归版本毕竟健壮性优先同时非递归的调试难度其实并没有比递归高多少。7.3 同一棵树的遍历结果不代表“唯一顺序”还有一个容易晕的点如果你在纸上手算遍历序列最好每次都用同一棵树画两遍一遍用“递归展开”的视角一遍用“栈模拟”的视角。我自己当年做过一个对比同时用两种视角走同一棵树写着写着就会发现栈模拟其实是递归展开的“底片”两者的轨迹完全重叠。一旦建立了这个对应关系后面看任何遍历代码都不觉得玄乎了。我在实际面试别人的时候发现能把单栈后序遍历写出来的人基本上对栈的理解已经过关了。所以如果你想检验自己到底懂没懂非递归遍历别只看前序和中序直接挑战后序。写不出来也不要紧照着前面那个单栈版本自己手动走一棵树把每个节点的压栈、出栈、打印时机全部记下来走完这一遍你就再也不会怕遍历了。