二叉树遍历这块说实话是算法面试里最容易被问“穿”的知识点。你打开任一份Java后端岗位的题库前中后序、层序遍历基本是标配而且面试官往往不会满足于你背出一种写法递归算过关紧接着就会追问一句“迭代怎么写”。很多人栽就栽在递归转迭代这一步其实核心就一句话递归靠系统栈迭代自己维护一个栈。把这事想通透二叉树遍历就算真正吃透了。这篇文章我把四种遍历方式全部过一遍递归和迭代都给出可直接运行的Java代码同时把为什么这么写、复杂度是多少、有什么坑都讲清楚。不管是正在刷题准备面试还是纯想补数据结构基础这篇都适合你反复看几遍。1. 遍历之前先把二叉树几个概念焊死1.1 前中后序到底在说什么先解决一个很多人面试时说糊涂的问题前序、中序、后序里的“序”指的是根节点什么时候被访问。前序遍历根 - 左 - 右中序遍历左 - 根 - 右后序遍历左 - 右 - 根这里的“左”和“右”不只是当前节点的左孩子和右孩子而是要递归地理解成“左子树”和“右子树”。你在脑子里过一遍这三个顺序会发现它们其实是在描述一种“行为规则”走到某个节点时是先处理根还是先处理左子树还是最后处理根。有一个直观但容易翻车的点前序遍历的第一个节点必然是整棵树的根后序遍历的最后一个节点也必然是根而中序遍历如果你不知道根的位置光靠一个序列是没法重建二叉树的。热搜里“关于二叉树前中后序遍历的常见问题”基本都围绕这种性质展开后面我专门用一节讲。1.2 为什么必须掌握递归和迭代两种姿势递归写法代码极短逻辑几乎就是把定义翻译成代码三行搞定。但递归有一个实际风险当二叉树退化成一条链比如每个节点只有右孩子递归深度会等于树的节点数Java默认的虚拟机栈很快就会被压爆抛栈溢出异常。迭代写法则是在手动模拟递归时系统帮我们做的那件事——用一个显式的栈来保存待访问的节点。它有两个优势一是不会因为树高过大而栈溢出二是能帮你真正理解遍历过程中“节点入栈出栈的时机”。所以我建议的学习路径是先把递归版本写得滚瓜烂熟再对照着递归的访问顺序去推导迭代版本。别跳步递归版本理解不透迭代版本大概率也会写得云里雾里。写代码之前先定义好树节点后面所有遍历都用它面试时直接默写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; } }2. 递归遍历所有遍历的地基2.1 递归的本质是系统栈递归为什么能实现“先处理完左子树再回来处理右子树”因为每次递归调用系统会把当前函数的状态压入调用栈等子调用返回后再从栈顶恢复现场继续执行。拿中序遍历来举例当你访问一个节点的左子树时当前节点和它的右子树信息都被存在栈帧里左子树全部处理完返回时再从栈帧里恢复当前节点输出它的值接着访问右子树。整个过程对代码来说是隐式的你不需要关心栈长什么样但脑子里要有这根弦——迭代版本就是把这个隐式栈手动实现出来。2.2 三种递归代码一次给齐前序遍历public void preorder(TreeNode root, ListInteger result) { if (root null) { return; } result.add(root.val); preorder(root.left, result); preorder(root.right, result); }中序遍历public void inorder(TreeNode root, ListInteger result) { if (root null) { return; } inorder(root.left, result); result.add(root.val); inorder(root.right, result); }后序遍历public void postorder(TreeNode root, ListInteger result) { if (root null) { return; } postorder(root.left, result); postorder(root.right, result); result.add(root.val); }代码几乎长一个样区别只在result.add(root.val)这一行的位置。把这三段对比着看你会发现递归遍历真正要记的只有一个套路先处理空节点返回再按“左、根、右”的语义安排三行代码的先后顺序。2.3 递归的代价与适用场景注意递归版本的空间复杂度不是 O(1)。每次递归调用都会占用栈空间最坏情况下树退化为链表空间复杂度会到 O(n)。这也是面试官追问迭代写法的核心动机之一。我见过不少人在递归函数里忘了写空判断public void preorder(TreeNode root, ListInteger result) { result.add(root.val); // root 为空时这里直接空指针 preorder(root.left, result); preorder(root.right, result); }这种代码在测试用例稍微给个空树就会崩。写递归的第一步永远是先处理终止条件这是我复盘过无数次踩坑后的经验。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; }这里有个细节Deque是 Java 里推荐用来当栈的接口ArrayDeque是它的常用实现。Stack类本身是遗留类线程安全带来的性能损耗在算法题里不值得。我刷了几百道题栈一律用ArrayDequepush/pop方法完全够用。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; }我理解这段代码时最喜欢用的生活类比是“进迷宫”你一直沿着左手边的墙走每经过一个岔路口就做个标记压栈走到死胡同了就退回上一个标记处弹栈看看标记点的右边有没有路有路继续走没路就再退回上一个标记。中序迭代的时间复杂度是 O(n)因为每个节点最多入栈一次、出栈一次空间复杂度最坏是 O(n)即树退化为链时栈里最多同时存 n 个节点。3.3 后序遍历面试里的拦路虎后序迭代比前序和中序都要绕因为根节点是最后访问的。你不能在第一次碰到根节点时就输出它必须等左子树和右子树都处理完之后才能输出。方法一双栈法这是我认为最简单好记的后序迭代方式。后序是左、右、根把它反过来就是根、右、左——你发现没有根、右、左刚好和前序遍历的根、左、右很像只是左右顺序反了。所以思路是先做一次“逆后序”遍历把结果存进第二个栈最后再全部弹出来得到的就是真正的后序顺序。public ListInteger postorderTraversal(TreeNode root) { ListInteger result new ArrayList(); if (root null) { return result; } DequeTreeNode stack new ArrayDeque(); DequeTreeNode output new ArrayDeque(); stack.push(root); while (!stack.isEmpty()) { TreeNode node stack.pop(); output.push(node); // 与前序遍历相反先压左再压右 if (node.left ! null) { stack.push(node.left); } if (node.right ! null) { stack.push(node.right); } } while (!output.isEmpty()) { result.add(output.pop().val); } return result; }双栈法的本质是“两次翻转”第一次把左、右、根变成根、右、左第二次把根、右、左再翻回来。理解了这一点你就不需要死记硬背代码了。方法二单栈 标记节点如果不想用两个栈还有一个“记录上一个访问节点”的思路由于根节点需要等到左右子树都访问完后才能输出所以当 cur 的左右孩子都为空或已经被访问过时才能输出 cur。public ListInteger postorderTraversal(TreeNode root) { ListInteger result new ArrayList(); DequeTreeNode stack new ArrayDeque(); TreeNode cur root; TreeNode prev null; while (cur ! null || !stack.isEmpty()) { while (cur ! null) { stack.push(cur); cur cur.left; } cur stack.peek(); // 右孩子为空或已被访问说明可以输出当前节点了 if (cur.right null || cur.right prev) { result.add(cur.val); stack.pop(); prev cur; cur null; } else { cur cur.right; } } return result; }这个写法的核心是prev指针。只要右孩子已经被处理过马上就能判断出当前节点已经是“左右都处理完”的状态可以直接输出。刷题时如果面试官不限制空间我一般直接写双栈法简单不容易出错如果面试官追问“能不能 O(1) 额外空间”再讨论 Morris 遍历或者这个单栈标记法。4. 层序遍历队列出场逐层收割4.1 标准层序遍历实现层序遍历和前中后序的思路完全不同。深度优先遍历用栈层序遍历用队列每次从队首取出一个节点访问它再把它左右孩子依次加入队尾。由于队列先进先出天然就能保证“同一层节点按从左到右的顺序被访问”。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; }很多人第一次写层序遍历时会在 while 循环里直接用queue.size()作为循环条件这是错的因为同一层出队的过程中下一层的节点已经进队了队列 size 一直在变。正确做法是在每层开始前先把当前层的节点数快照下来也就是代码里的int size queue.size()这一行。把返回值设计成ListListInteger的好处是每一层单独一个列表方便你按层处理数据。比如统计每一层的最大值、求层内平均值都只需要对这个两层结构做一次循环。4.2 层序遍历的常见变种之字形遍历之字形遍历是层序遍历的高频扩展题第一层从左到右第二层从右到左第三层再从左到右以此类推。实现起来有两种思路。第一种是层序遍历遇到偶数层从 0 算起或从 1 算起要提前约定好时把该层列表反转第二种是维护一个双向队列奇数层从队尾入队、偶数层从队头入队或者反过来。我更推荐第一种因为代码改动量最小不容易出错public ListListInteger zigzagLevelOrder(TreeNode root) { ListListInteger result new ArrayList(); if (root null) { return result; } QueueTreeNode queue new LinkedList(); queue.offer(root); boolean reverse false; 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); } } if (reverse) { Collections.reverse(level); } result.add(level); reverse !reverse; } return result; }这里用 boolean 变量reverse做层序标记每处理完一层就翻转一次。需要特别注意反转的是level这个列表不是队列里的节点顺序。有些人会想在入队时就调整左右孩子入队顺序来实现之字形但这样做会直接破坏下一层的访问顺序逻辑实战中非常容易出 bug我踩过这个坑后来一律先层序再反转。5. 高频问题与实战排雷这轮讲完基本就是面经5.1 时间复杂度与空间复杂度速查面试官很喜欢在遍历题后面跟一句“复杂度是多少”下面这个表基本可以直接背遍历方式时间复杂度空间复杂度最坏核心数据结构前序递归O(n)O(n)系统栈前序迭代O(n)O(n)显式栈中序递归O(n)O(n)系统栈中序迭代O(n)O(n)显式栈后序递归O(n)O(n)系统栈后序迭代双栈O(n)O(n)两个栈层序迭代O(n)O(n)队列时间都是 O(n)因为每个节点都被访问一次且仅被访问一次。空间这块平衡二叉树的情况下栈或队列里最多存 O(log n) 个节点但是面试题默认讨论最坏情况树退化成链时直接按 O(n) 回答比较稳妥。5.2 遍历顺序相关的高频提问给定前序和中序能唯一确定一棵二叉树吗能。前序确定根中序确定左右子树范围递归切分即可。给定后序和中序能唯一确定一棵二叉树吗能。后序最后一个节点是根中序辅助切分。给定前序和后序能唯一确定一棵二叉树吗不能。前序和后序只能确定根的位置但无法区分左右子树的边界。比如一个只有左孩子的链和一个只有右孩子的链前序和后序序列可能完全一样。这些结论在面试里常常以“请你重建二叉树”的形式出现本质上考的还是遍历顺序的语义。LeetCode 105、106 两道经典题就是干这个的建议刷一遍。热水词里还有“二叉树的深度”。最大深度说白了就是后序遍历的变体左子树深度和右子树深度取最大值再加 1。代码甚至可以写成一行的递归public int maxDepth(TreeNode root) { return root null ? 0 : 1 Math.max(maxDepth(root.left), maxDepth(root.right)); }这里也用到了后序思想——先算出左右子树的结果再汇总到当前节点。5.3 递归转迭代的通用思路我在实战中发现所有递归能改写成迭代的算法思路都是同一个模板想想递归函数执行时系统栈里存了什么然后手动用栈去模拟。前序入栈时立刻访问所以“弹出即访问”。中序入栈时要等左子树处理完所以“左链全部压栈弹出时访问再转向右”。后序入栈后要等左右子树都处理完所以“要么双栈翻转要么标记右孩子是否已访问”。把这个模板想清楚你面对任何“用迭代实现树的某某操作”的题目都不会慌因为底层逻辑是统一的。搜索引擎里“迭代和递归的区别举例”这类问题本质就是在问“递归如何变成循环加栈”。我把这个模板总结为三句话递归压栈做什么迭代就压什么递归什么时候返回迭代就什么时候弹栈递归在哪里拼接结果迭代就把访问操作放在哪里。5.4 现场实战完整可运行的测试代码纸上谈兵没用我把几种遍历串起来写个 main 方法构造一棵简单二叉树跑一遍。树的形状如下1 / \ 2 3 / \ \ 4 5 6测试代码public class BinaryTreeTraversalDemo { public static void main(String[] args) { TreeNode root new TreeNode(1); root.left new TreeNode(2); root.right new TreeNode(3); root.left.left new TreeNode(4); root.left.right new TreeNode(5); root.right.right new TreeNode(6); BinaryTreeTraversalDemo demo new BinaryTreeTraversalDemo(); System.out.println(前序: demo.preorderTraversal(root)); System.out.println(中序: demo.inorderTraversal(root)); System.out.println(后序: demo.postorderTraversal(root)); System.out.println(层序: demo.levelOrder(root)); System.out.println(之字: demo.zigzagLevelOrder(root)); } // 前序迭代 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; } // 中序迭代 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; } // 后序迭代 - 双栈法 public ListInteger postorderTraversal(TreeNode root) { ListInteger result new ArrayList(); if (root null) { return result; } DequeTreeNode stack new ArrayDeque(); DequeTreeNode output new ArrayDeque(); stack.push(root); while (!stack.isEmpty()) { TreeNode node stack.pop(); output.push(node); if (node.left ! null) { stack.push(node.left); } if (node.right ! null) { stack.push(node.right); } } while (!output.isEmpty()) { result.add(output.pop().val); } return result; } // 层序遍历 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; } // 之字形层序遍历 public ListListInteger zigzagLevelOrder(TreeNode root) { ListListInteger result new ArrayList(); if (root null) { return result; } QueueTreeNode queue new LinkedList(); queue.offer(root); boolean reverse false; 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); } } if (reverse) { Collections.reverse(level); } result.add(level); reverse !reverse; } return result; } }这段代码复制粘贴就能跑预期输出前序 [1, 2, 4, 5, 3, 6]中序 [4, 2, 5, 1, 3, 6]后序 [4, 5, 2, 6, 3, 1]层序 [[1], [2, 3], [4, 5, 6]]之字 [[1], [3, 2], [4, 5, 6]]跑完这几个输出你对遍历顺序的理解会特别具象。我面试前就喜欢拿上面这棵树做快速自检三分钟内能把五种遍历全部写一遍肌肉记忆基本就牢了。5.5 几个容易踩的坑与排查思路第一个坑是前面提过的层序遍历里循环条件误用了动态的queue.size()这个错误特别隐蔽因为树只有一层时看不出来一旦多层就会出现“一层被拆成多份”的诡异输出。排查方法很简单单步调试时盯着每一轮 while 之前和之后的队列大小就能看到 size 在变。第二个坑是迭代遍历里忘了判空。前序迭代里如果root为 null 就直接stack.push(root)运行时会抛空指针异常。我建议所有遍历方法的第一步都养成习惯写上if (root null) return 空结果;别觉得啰嗦这是空树用例的保命符。第三个坑是后序迭代里cur null和cur cur.right的时机。很多新手在这个位置徘徊很久如果当前节点的右孩子已经处理完了必须把cur置为 null否则外层循环会把已经处理完的右子树再压一遍栈导致死循环。理解prev指针和cur状态之间的关系是所有后序迭代写法里最容易卡住的地方。还有一类问题是“为什么我一写二叉树程序就报运行时错误”这种人大概率症状是两种递归没有明确的终止条件导致栈溢出或者迭代时对 stack / queue 弹空。要么在入口判空要么在循环里时刻检查容器是否为空这两个习惯养成了90% 的运行时错误能避免。最后再分享一个备考的小习惯我刷题时会把每种遍历都贴到本地 IDE 里专门建一个测试类每次写完新解法立刻跑固定用例对比输出。遍历顺序这个东西光看代码总觉得懂了但跑一遍结果、亲眼看到中序输出是有序的如果是二叉搜索树那种感觉是完全不一样的。算法这东西没有捷径手写代码跑通比看十遍教程都有用。