二叉树遍历全攻略：递归、迭代与层序的代码实现与避坑指南

二叉树遍历这块，说难也难，说简单也简单。难是因为很多朋友在递归改迭代这一步卡住，简单是因为只要理解了“递归序”和“栈的模拟过程”，前中后序加层序就是一马平川的事情。

我自己当年刷这块的时候也走过弯路：前序迭代照猫画虎能写出来，一到中序和后序就抓瞎，后来才发现是没搞懂“什么时候访问节点”和“什么时候处理右子树”的本质。这篇博文把递归、迭代、层序三种思路一次性讲透，代码可以直接抄，抄完建议按文末的排查清单自己动手跑一遍。

1. 二叉树遍历的整体设计思路：先搞懂你要解决什么问题

1.1 什么是前序、中序、后序、层序遍历

二叉树的遍历，本质上就是“按某种规则，把树里的每个节点都访问一次”。前序、中序、后序这三个名字，指的是根节点在访问顺序中的位置：

• 前序遍历：根 -> 左 -> 右
• 中序遍历：左 -> 根 -> 右
• 后序遍历：左 -> 右 -> 根

而层序遍历则是按层从上到下、从左到右访问，像读文章一样一行一行扫过去。

很多初学者只看这个规则会觉得很简单，但实际动手写代码时，最容易犯的错就是把“访问”和“递归调用”的顺序搞混。我建议你先记住一句话：前中后序遍历的本质是“递归序”的变体。递归遍历一棵树时，每个节点其实会被经过三次：第一次是从父节点下来，第二次是从左子树回来，第三次是从右子树回来。前序就是在第一次经过时打印节点，中序是第二次经过时打印，后序是第三次经过时打印。

1.2 递归和迭代的选型逻辑

很多人问我：“面试时候到底写递归还是迭代？”我的答案是：两个都要会。

递归方式代码简洁，和树的定义天然契合，理解起来很直观，适合快速解题和表达思路。但它有个硬伤：当树的深度很大时，递归会导致栈溢出。Java虚拟机默认的线程栈大小是1MB左右，每层递归调用都会占用栈帧，树深达到万级甚至十万级就可能直接抛StackOverflowError。

迭代方式用显式的栈模拟递归过程，虽然代码写起来更啰嗦，但栈空间可控，不会因为树的深度过大而崩溃。更重要的是，面试官特别喜欢在递归完成后追问一句“能不能用迭代实现？”，这本质上是在考察你对函数调用栈的理解程度。

层序遍历则完全是另一套思路，它和树的深度没关系，用的是队列先进先出的特性，天然适合逐层处理。注意一个细节：层序遍历用递归也能写，但实现起来非常别扭，需要通过depth参数记录当前层数，还要处理List的扩容，远不如队列直观。所以我在实际做题时，遇到“按层”两个字，第一反应就是队列。

1.3 前置准备：二叉树的节点定义与测试用例

正式写遍历代码之前，先把公共的节点类和构建树的代码准备好。这里我按LeetCode上最常见的定义来写：

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; } }

测试树我一律用下面这棵，结构简单但能覆盖所有情况：

1 / \ 2 3 / \ \ 4 5 6

构建代码：

public static TreeNode buildTree() { TreeNode node4 = new TreeNode(4); TreeNode node5 = new TreeNode(5); TreeNode node6 = new TreeNode(6); TreeNode node2 = new TreeNode(2, node4, node5); TreeNode node3 = new TreeNode(3, null, node6); return new TreeNode(1, node2, node3); }

这棵树的遍历结果分别是：

• 前序：1 2 4 5 3 6
• 中序：4 2 5 1 3 6
• 后序：4 5 2 6 3 1
• 层序：1 2 3 4 5 6

我建议你把这几个结果抄在便利贴上，写代码前先看一眼，写完代码后对着结果验证，比你盲写一百遍记忆都深刻。

2. 递归遍历：代码最简洁，但要理解递归三要素

2.1 递归三要素：终止条件、返回值、单层逻辑

递归解法看起来简单，但能不能一遍写对，取决于你是否有意识地在动手前拆解递归三要素：

1. 终止条件：当前节点为null，直接return，这是递归的出口。
2. 返回值：遍历类题目大多数不需要返回值，结果保存在外部集合中。
3. 单层逻辑：确定当前层要做什么操作。前序就是“先打印自己，再处理左右子树”，中序就是“先处理左子树，再打印自己，最后处理右子树”，后序就是“先处理左右子树，最后打印自己”。

以中序遍历为例，代码长这样：

public List<Integer> inorderTraversal(TreeNode root) { List<Integer> result = new ArrayList<>(); inorder(root, result); return result; } private void inorder(TreeNode node, List<Integer> result) { if (node == null) { return; } inorder(node.left, result); result.add(node.val); inorder(node.right, result); }

前序和后序只需要调整result.add(node.val)这一行的位置，其他结构完全一致：

// 前序遍历 private void preorder(TreeNode node, List<Integer> result) { if (node == null) { return; } result.add(node.val); preorder(node.left, result); preorder(node.right, result); } // 后序遍历 private void postorder(TreeNode node, List<Integer> result) { if (node == null) { return; } postorder(node.left, result); postorder(node.right, result); result.add(node.val); }

这里有个值得注意的小坑：很多人写递归遍历时，喜欢把result作为参数传来传去，却忘了在递归返回后维护集合状态。对于遍历来说这没有问题，因为我们是往集合里添加元素，不会因为回溯而删除。但如果你在练习回溯类题目（比如路径总和、全排列），就必须在递归返回后“撤销”上一次的选择。这个区别一定要分清，否则后序学到回溯时会很痛苦。

2.2 递归底层的栈机制：为什么递归天然就是深度优先

递归之所以能实现“先走到最底层，再逐层返回”，靠的是JVM的函数调用栈。每次递归调用都会在栈上压入一个新的栈帧，里面保存了当前函数的局部变量和执行位置。当递归到达终止条件时，栈帧从栈顶依次弹出，程序回到上一层调用点继续执行。

拿前序遍历举个例子。你调用preorder(root)时，栈里先压入对根节点的调用。这个调用打印1后，又压入对左子节点的调用，打印2；对2的调用又压入对4的调用，打印4。直到4的左右子节点都为null，递归开始返回，依次处理5、3、6。整个过程就像在树上做了一次“走到底再回头”的探索，这就是深度优先搜索（DFS）的底层逻辑。

理解了这个机制，你就能回答面试里常问的一个问题：“递归和迭代有什么区别？”我的经验是，从执行模型上说，递归是用系统栈，迭代是你自己维护栈。从代码表达上说，递归更贴近数学归纳法，迭代更贴近状态机。从性能上说，递归因为有额外的函数调用开销，通常比迭代慢一些，但复杂度量级是一样的。

2.3 递归的注意点：什么时候不能用递归

虽然递归代码写起来非常爽，但有两个场景建议你主动避开：

• 树的深度非常大。比如一条链状的树，节点数几万时，递归可能直接栈溢出。刷题时可能碰不到这么大的数据，但真实业务中，如果从数据库查出一棵深度不确定的组织架构树，递归前最好先评估一下深度。
• 需要频繁修改树结构。递归遍历过程中如果同时做节点的增删，很容易因为指针变化导致死循环或空指针。这种情况下我会先遍历收集节点引用，再统一处理，而不是在递归回调里直接修改。

注意：面试中如果使用递归，最好主动提一句“递归的缺点是极端情况下会栈溢出，如果需要更健壮，可以用迭代栈来实现”。这句话能体现你思考过边界条件，而不是只会背题。

3. 迭代遍历：用栈模拟递归的核心技巧

3.1 前序遍历的迭代实现：最简单的入口

前序遍历的迭代思路最容易理解：先把根节点入栈，然后循环执行“弹栈 -> 访问 -> 右孩子入栈 -> 左孩子入栈”。这里有个顺序问题：因为栈是后进先出，想先处理左子树，就得先把右子树压入栈底，再把左子树压到栈顶。

直接上代码：

public List<Integer> preorderTraversal(TreeNode root) { List<Integer> result = new ArrayList<>(); if (root == null) { return result; } Deque<TreeNode> stack = new ArrayDeque<>(); 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; }

很多人第一次写迭代前序时，会纠结“要不要判空再压栈”。这里我建议判空，把空节点挡在栈外，这样后面while循环里弹出节点后可以直接访问，不用再判断一次node == null。如果你不判空直接压入null，弹出时就必须多一个if判断，代码会更啰嗦，也更容易在边界条件下出错。

3.2 中序遍历的迭代实现：一直往左走到底

中序迭代比前序难理解，原因在于中序的顺序是“左 -> 根 -> 右”，根节点第一次经过时不能马上访问，得先处理完左子树回过头来才能访问。用一句口诀概括：一路向左压栈，弹栈访问，再往右走。

public List<Integer> inorderTraversal(TreeNode root) { List<Integer> result = new ArrayList<>(); 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(); result.add(cur.val); cur = cur.right; } return result; }

我在教别人的时候，喜欢把这个过程和“走迷宫”类比：你沿着左边的墙一直走，走到死胡同（没有左孩子）时，退一格处理当前节点，然后看看右边有没有路，有就往右拐，右拐后再继续沿左边的墙走。

这个写法非常经典，建议背到肌肉记忆。面试时，中序迭代是高频考点，因为二叉搜索树的中序遍历结果是递增序列，很多题目（比如验证二叉搜索树）都会用到这个性质。

3.3 后序遍历的迭代实现：两种思路，推荐反转法

后序迭代是三种里最麻烦的，因为根节点的访问被排到了最后。如果你直接按后序的顺序去模拟，会发现需要额外记录“右子树是否已经处理过”的状态，代码会变得很复杂。

这里分享一个取巧但非常实用的技巧：前序遍历是“根左右”，如果把左右孩子的压栈顺序反一下，变成“根右左”，再把结果反转，不就是“左右根”的后序遍历了吗？

实现起来很简单：

public List<Integer> postorderTraversal(TreeNode root) { LinkedList<Integer> result = new LinkedList<>(); if (root == null) { return result; } Deque<TreeNode> stack = new ArrayDeque<>(); stack.push(root); while (!stack.isEmpty()) { TreeNode node = stack.pop(); result.addFirst(node.val); // 头插法，相当于反转 if (node.left != null) { stack.push(node.left); } if (node.right != null) { stack.push(node.right); } } return result; }

注意这里我把result声明成了LinkedList，用addFirst实现头插。头插的结果就是：最先弹出的根节点被放到了最后，右子树节点的顺序也被整体反转，最终得到的正好是后序遍历。

如果你不想用addFirst，也可以正常用add收集“根右左”的结果，最后再统一Collections.reverse(result)，效果一样。我个人更喜欢addFirst，因为少一次整体反转，效率略高那么一丁点。

另一种双栈法也是一种标准解法，但需要两个栈，代码可读性不如反转法。我的建议是：选一种你理解最深的记牢，不要贪多。面试时能写对一种就够了，写两种反而容易混乱。

3.4 三种迭代遍历的对比速查表

总结成一句话：前序是“来一个处理一个”，中序是“先到底层再回头处理”，后序是“用前序的壳，装反序的核”。

4. 层序遍历：队列的教科书级应用

4.1 层序遍历的标准模板：队列 + 每层循环

层序遍历也叫广度优先搜索（BFS）在二叉树上的直接应用。核心数据结构是队列，核心逻辑是：把根节点入队，然后循环处理队首节点，同时把它的左右孩子依次入队。

但如果我们只做简单的出队入队，输出结果是1 2 3 4 5 6这样的“大平层”顺序，看不出是哪一层的。真正做层序遍历的题目时，通常要求按层输出，这个时候需要用一个小技巧：在每层开始处理前，先记录当前队列的大小size，然后只处理size个节点。

public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> result = new ArrayList<>(); if (root == null) { return result; } Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); while (!queue.isEmpty()) { int size = queue.size(); List<Integer> level = new ArrayList<>(); for (int i = 0; i < size; i++) { TreeNode node = queue.poll(); level.add(node.val); if (node.left != null) { queue.offer(node.left); } if (node.right != null) { queue.offer(node.right); } } result.add(level); } return result; }

这里有一个非常关键的小细节：for循环里的size必须在循环开始前先取出来存好。如果直接在for循环里写i < queue.size()，因为循环过程中队列里会不断加入新节点，queue.size()是动态变化的，你会把下一层的节点也当成当前层处理，输出就全乱套了。这个问题我在带新人时见过不下五次，几乎每个人第一次写都会踩一次。

4.2 队列操作的细节：offer、poll与peek的选择

Java里操作队列时，有两个方法对容易混淆：offer和add、poll和remove、peek和element。

• add在队列满时抛异常，offer返回false。无限容量的LinkedList通常不会满，但为了代码健壮性，我习惯用offer。
• remove在队列为空时抛异常，poll返回null。遍历场景下，当我们用while (!queue.isEmpty())保证循环时才调用poll，两者都可以，但poll更安全，不需要额外处理异常。

Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); // 入队 TreeNode node = queue.poll(); // 出队，空时返回null TreeNode top = queue.peek(); // 查看队首，不出队

4.3 层序遍历的变体：之字形遍历和二叉树深度

层序遍历的模板掌握好之后，很多二叉树题目都能套用。面试中最高频的两个变体是：

（1）之字形遍历（锯齿形遍历）

奇数层从左往右，偶数层从右往左。最简单的实现是在层序遍历的基础上，用一个布尔变量记录当前层的方向，如果是反向层就Collections.reverse(level)后再加入结果；或者用双端队列LinkedList，根据方向决定是addLast还是addFirst。

public List<List<Integer>> zigzagLevelOrder(TreeNode root) { List<List<Integer>> result = new ArrayList<>(); if (root == null) { return result; } Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); boolean leftToRight = true; while (!queue.isEmpty()) { int size = queue.size(); LinkedList<Integer> level = new LinkedList<>(); for (int i = 0; i < size; i++) { TreeNode node = queue.poll(); if (leftToRight) { level.addLast(node.val); } else { level.addFirst(node.val); } if (node.left != null) { queue.offer(node.left); } if (node.right != null) { queue.offer(node.right); } } result.add(level); leftToRight = !leftToRight; } return result; }

（2）求二叉树的最大深度

这题用递归做很爽，三行结束：

public int maxDepth(TreeNode root) { if (root == null) { return 0; } return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1; }

但用层序遍历也有个额外的好处：能直接数出树的层数。每处理一层，深度加一，循环结束后就是最大深度。面试时随口提一句“层序遍历也能求深度，但需要额外队列空间，O(n)”，会显得你理解很全面。

5. 二叉树遍历的常见问题与避坑手册

5.1 为什么递归写法里result集合要用外部引用传递

很多初学者会直接把List<Integer>作为递归函数的返回值，试图用“拼接返回列表”的方式写遍历。比如：

public List<Integer> inorder(TreeNode root) { List<Integer> result = new ArrayList<>(); if (root == null) { return result; } result.addAll(inorder(root.left)); result.add(root.val); result.addAll(inorder(root.right)); return result; }

这段代码逻辑上没错，但会创建大量临时List，内存消耗大，性能也差。相比之下，用一个外部集合一路传下去，每个节点只需要O(1)的add操作。我在实际做题时，优先用外部引用，只有在API设计不允许额外传参时才用拼接方式。

5.2 迭代遍历时反复出现的ArrayDeque与Stack之争

我在用迭代写栈时，里面一律用ArrayDeque而不是Stack。原因有两点：

• Stack继承自Vector，所有方法都加了synchronized锁，性能有额外开销。
• Stack的pop()方法在栈为空时抛EmptyStackException，而ArrayDeque的pop()也是抛异常，但在做判空场景下，用push/pop语义更清晰，且没有同步锁开销。

如果你非要用Stack，也能跑通，但面试时如果被问到“你为什么不直接用Stack”，能答出性能原因绝对是加分项。LinkedList也可以当栈用，但底层是双向链表，每个节点有额外的前驱后继指针，内存占用比ArrayDeque大。所以我的默认选择是：栈用ArrayDeque，队列用LinkedList。

5.3 遍历中修改树结构导致死循环

我在做“删除二叉树中的某个节点”这类需求时，踩过一个坑：在层序遍历过程中直接对队列里的节点做断链操作，结果该节点的子节点已经不再指向原来的孩子，而队列里还留着旧的引用，导致后续处理逻辑出错。

正确的做法是先遍历收集所有需要处理的节点引用，等遍历完成后再统一修改树结构。遍历和修改混在一起，很容易让指针乱掉，尤其是递归删除时还容易触发ConcurrentModificationException或者循环引用。

5.4 常见问题速查表

5.5 调试遍历代码的三步法

如果你写出的遍历结果不对，先别急着一行行读代码，按这三步排查效率最高：

1. 拿纸画树，把每个节点的遍历顺序手写出来。
2. 在代码里打印关键信息：每次入栈/出栈的节点值、每次进入/离开递归函数的节点值。我调试时经常这么写：System.out.println("push: " + node.val)。
3. 把打印结果和你手写的结果对比，找出第一个不一致的地方，那基本就是出错的位置。

对递归代码，还有一个百试百灵的心法：假设递归函数已经写对了，不要一层层钻进去验证。比如中序遍历时，你调用inorder(node.left)就默认它已经把左子树按中序访问完了，只需要关注当前层做什么。很多人在递归里迷路，就是因为总想着把递归调动过程在脑子里全展开，这反而会把简单问题复杂化。递归是数学归纳法，不是循环展开。

最后说两句实在话

我带过不少准备面试的朋友，发现大家学二叉树遍历时最大的障碍不是理解算法，而是陷入“背代码”的陷阱。前序背一套、中序背一套、后序背一套，层序再背一套，一旦面试官稍微变个型，比如“之字形遍历”或者“请你用迭代实现后序”，立马就懵了。

我个人更推荐按照“一个递归序 -> 两个栈技巧 -> 一个队列模板”的框架去学：只要理解了递归序，三种递归遍历就是同一段代码换个位置；只要理解了前序遍历的栈模拟，后序遍历就是在前序基础上反一下；只要理解了队列加size快照，层序、之字形、按层求和都是同一个模板。我在带人的时候总爱说一句话：别背代码，背过程。把过程想清楚了，代码自然就写出来了。