企业官网建设流程全解析

很多人问我，二叉树的三种遍历到底怎么理解才透彻。说实话，这类问题在网上随便一搜就是一大把教程，但大多只是把递归代码贴出来，再配一张三种遍历访问顺序的表格。看得多了你会发现一个尴尬的局面：代码背得滚瓜烂熟，表格也记住了“前序根左右、中序左根右、后序左右根”，可一旦碰到几道变体题，比如让你写个非递归的后序遍历，或者让你用遍历序列重建二叉树，立刻卡壳。

这篇文章我打算换个讲法，不急着堆代码，先带着你把三种遍历的本质逻辑过一遍，再把“为什么代码要那么写”“为什么后序的非递归那么别扭”这些藏在角落里的东西挖出来。内容面向刚学完树结构、准备笔试面试，或者想彻底打通这块知识点的读者，我尽量做到既有直观逻辑，也能直接上手写。

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. 从根节点1进入，inOrder(1)压栈。
2. inOrder(1)先调用左子树，inOrder(2)压栈。
3. 进入inOrder(2)，又先调用它的左子树，inOrder(4)压栈。
4. inOrder(4)的左孩子是null，直接返回。此时inOrder(4)还没打印任何东西，接着执行打印，输出“4”。
5. 然后调用4的右孩子，也是null，返回。inOrder(4)执行完毕，出栈。
6. 回到inOrder(2)，刚才卡在调用左子树那一步，现在左子树整体返回了，接着打印“2”。
7. 调用2的右子树，inOrder(5)压栈。
8. 5有左孩子null，跳过；打印“5”；5的右孩子是7，继续inOrder(7)压栈。
9. 7左孩子null，打印“7”，右孩子null，返回，7出栈。
10. 5处理完出栈，回到2，2也处理完出栈，回到1的调用。
11. 此时打印“1”，然后再进入右子树，按相同逻辑输出3、6。

最终中序输出：4 2 7 5 1 3 6。

这个过程我想要你记住一件事：每个递归函数在执行时，并不是“一口气”跑完的，它会卡在调用左子树的那个位置，等左子树整棵返回之后才继续。这个“卡住”的动作，就是系统栈把它压在那里的原因。理解了这个，再看非递归实现，思路立刻就清楚了——我们要做的，就是用自己管理的栈，模拟这种“卡住再回来”的过程。

2.2 前序和后序的递归轨迹差别

前序是最符合人类直觉的，进去就打印，所以它的轨迹基本就是“走到哪打印到哪”，系统栈的深度决定了路径的深度。后序则相反，一个节点要等左右两棵子树全部返回才能打印，这意味着在系统栈里，这个节点的“活着时间”是所有遍历中最久的。

这也是为什么后序遍历在工程上经常被用来做树的销毁或内存释放——你必须先处理完孩子，才能释放父节点，否则孩子就丢了。顺带一提，很多树的题目里，凡是涉及“从底向上汇总”的逻辑，比如判断平衡二叉树、计算树的高度，基本都是后序的骨架，因为需要先拿到左右子树的结果，才能算当前节点。

3. 非递归实现：真正检验你懂不懂“栈”的时候

3.1 前序非递归：唯一一个简单到不需要思考的

前序非递归用栈模拟，思路很顺：根先入栈，然后循环，弹出一个节点，打印，再把右孩子压入栈，再压左孩子。为什么要先压右再压左？因为栈是后进先出，先压右边，左边后压，下一次弹出来的就是左孩子，如此才能保证“根-左-右”的访问顺序。

void preOrderIter(TreeNode root) { if (root == null) return; Deque<TreeNode> 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) { Deque<TreeNode> 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) { Deque<TreeNode> stack = new ArrayDeque<>(); Deque<Integer> 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) { Deque<TreeNode> 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，步骤如下：

1. 前序数组的第一个元素就是整棵树的根。
2. 在中序数组中找到这个根的位置index，index左边的全部属于左子树，右边全部属于右子树。
3. 根据左子树的节点个数，去前序数组中切分出对应的左子树前序段和右子树前序段。
4. 递归重建左右子树。

Java递归写法大概长这样：

TreeNode buildTree(int[] preorder, int[] inorder) { Map<Integer, 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, Map<Integer, 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 同一棵树的遍历结果不代表“唯一顺序”

还有一个容易晕的点：如果你在纸上手算遍历序列，最好每次都用同一棵树画两遍，一遍用“递归展开”的视角，一遍用“栈模拟”的视角。我自己当年做过一个对比，同时用两种视角走同一棵树，写着写着就会发现，栈模拟其实是递归展开的“底片”，两者的轨迹完全重叠。一旦建立了这个对应关系，后面看任何遍历代码都不觉得玄乎了。

我在实际面试别人的时候发现，能把单栈后序遍历写出来的人，基本上对栈的理解已经过关了。所以如果你想检验自己到底懂没懂非递归遍历，别只看前序和中序，直接挑战后序。写不出来也不要紧，照着前面那个单栈版本，自己手动走一棵树，把每个节点的压栈、出栈、打印时机全部记下来，走完这一遍，你就再也不会怕遍历了。