二叉树遍历这块说难也难说简单也简单。难是因为很多朋友在递归改迭代这一步卡住简单是因为只要理解了“递归序”和“栈的模拟过程”前中后序加层序就是一马平川的事情。我自己当年刷这块的时候也走过弯路前序迭代照猫画虎能写出来一到中序和后序就抓瞎后来才发现是没搞懂“什么时候访问节点”和“什么时候处理右子树”的本质。这篇博文把递归、迭代、层序三种思路一次性讲透代码可以直接抄抄完建议按文末的排查清单自己动手跑一遍。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 递归三要素终止条件、返回值、单层逻辑递归解法看起来简单但能不能一遍写对取决于你是否有意识地在动手前拆解递归三要素终止条件当前节点为null直接return这是递归的出口。返回值遍历类题目大多数不需要返回值结果保存在外部集合中。单层逻辑确定当前层要做什么操作。前序就是“先打印自己再处理左右子树”中序就是“先处理左子树再打印自己最后处理右子树”后序就是“先处理左右子树最后打印自己”。以中序遍历为例代码长这样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); }前序和后序只需要调整result.add(node.val)这一行的位置其他结构完全一致// 前序遍历 private void preorder(TreeNode node, ListInteger result) { if (node null) { return; } result.add(node.val); preorder(node.left, result); preorder(node.right, result); } // 后序遍历 private void postorder(TreeNode node, ListInteger 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 ListInteger preorderTraversal(TreeNode root) { ListInteger result new ArrayList(); if (root null) { return result; } DequeTreeNode 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 ListInteger inorderTraversal(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; }我在教别人的时候喜欢把这个过程和“走迷宫”类比你沿着左边的墙一直走走到死胡同没有左孩子时退一格处理当前节点然后看看右边有没有路有就往右拐右拐后再继续沿左边的墙走。这个写法非常经典建议背到肌肉记忆。面试时中序迭代是高频考点因为二叉搜索树的中序遍历结果是递增序列很多题目比如验证二叉搜索树都会用到这个性质。3.3 后序遍历的迭代实现两种思路推荐反转法后序迭代是三种里最麻烦的因为根节点的访问被排到了最后。如果你直接按后序的顺序去模拟会发现需要额外记录“右子树是否已经处理过”的状态代码会变得很复杂。这里分享一个取巧但非常实用的技巧前序遍历是“根左右”如果把左右孩子的压栈顺序反一下变成“根右左”再把结果反转不就是“左右根”的后序遍历了吗实现起来很简单public ListInteger postorderTraversal(TreeNode root) { LinkedListInteger result new LinkedList(); if (root null) { return result; } DequeTreeNode 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 三种迭代遍历的对比速查表遍历方式核心思路关键点适用场景前序迭代弹出即访问先压右再压左根节点最先处理最简单复制二叉树、求叶子节点中序迭代一路向左压栈弹栈访问转向右cur指针反复横跳二叉搜索树相关、递增序列判断后序迭代前序变体“根右左”后反转利用List头插或Collections.reverse删除二叉树、表达式树求值总结成一句话前序是“来一个处理一个”中序是“先到底层再回头处理”后序是“用前序的壳装反序的核”。4. 层序遍历队列的教科书级应用4.1 层序遍历的标准模板队列 每层循环层序遍历也叫广度优先搜索BFS在二叉树上的直接应用。核心数据结构是队列核心逻辑是把根节点入队然后循环处理队首节点同时把它的左右孩子依次入队。但如果我们只做简单的出队入队输出结果是1 2 3 4 5 6这样的“大平层”顺序看不出是哪一层的。真正做层序遍历的题目时通常要求按层输出这个时候需要用一个小技巧在每层开始处理前先记录当前队列的大小size然后只处理size个节点。public ListListInteger levelOrder(TreeNode root) { ListListInteger result new ArrayList(); if (root null) { return result; } QueueTreeNode queue new LinkedList(); queue.offer(root); while (!queue.isEmpty()) { int size queue.size(); ListInteger 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更安全不需要额外处理异常。QueueTreeNode 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 ListListInteger zigzagLevelOrder(TreeNode root) { ListListInteger result new ArrayList(); if (root null) { return result; } QueueTreeNode queue new LinkedList(); queue.offer(root); boolean leftToRight true; while (!queue.isEmpty()) { int size queue.size(); LinkedListInteger 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集合要用外部引用传递很多初学者会直接把ListInteger作为递归函数的返回值试图用“拼接返回列表”的方式写遍历。比如public ListInteger inorder(TreeNode root) { ListInteger 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 常见问题速查表典型症状根本原因解决办法递归遍历时StackOverflowError树太深JVM栈空间耗尽改用迭代栈或调大线程栈-Xss层序遍历把多层混在一起了for循环里用了动态变化的queue.size()循环前先用局部变量存size迭代中序循环条件写错导致死循环cur没有在每次循环末尾右移写完cur node.right后确保外层循环能更新cur前序迭代先压了左孩子弹出时左孩子被压在右孩子下面顺序反了记住“想先处理谁谁最后入栈”后序遍历要求结果顺序为左右根但写成了根右左没有做反转用addFirst或Collections.reverse空树输入返回了null而不是空列表没有判空直接操作root函数开头if (root null) return new ArrayList()或return用add操作队列在边界处抛异常add队列满时会抛异常统一改用offer5.5 调试遍历代码的三步法如果你写出的遍历结果不对先别急着一行行读代码按这三步排查效率最高拿纸画树把每个节点的遍历顺序手写出来。在代码里打印关键信息每次入栈/出栈的节点值、每次进入/离开递归函数的节点值。我调试时经常这么写System.out.println(push: node.val)。把打印结果和你手写的结果对比找出第一个不一致的地方那基本就是出错的位置。对递归代码还有一个百试百灵的心法假设递归函数已经写对了不要一层层钻进去验证。比如中序遍历时你调用inorder(node.left)就默认它已经把左子树按中序访问完了只需要关注当前层做什么。很多人在递归里迷路就是因为总想着把递归调动过程在脑子里全展开这反而会把简单问题复杂化。递归是数学归纳法不是循环展开。最后说两句实在话我带过不少准备面试的朋友发现大家学二叉树遍历时最大的障碍不是理解算法而是陷入“背代码”的陷阱。前序背一套、中序背一套、后序背一套层序再背一套一旦面试官稍微变个型比如“之字形遍历”或者“请你用迭代实现后序”立马就懵了。我个人更推荐按照“一个递归序 - 两个栈技巧 - 一个队列模板”的框架去学只要理解了递归序三种递归遍历就是同一段代码换个位置只要理解了前序遍历的栈模拟后序遍历就是在前序基础上反一下只要理解了队列加size快照层序、之字形、按层求和都是同一个模板。我在带人的时候总爱说一句话别背代码背过程。把过程想清楚了代码自然就写出来了。
