引言二叉树遍历是算法工程师面试的“第一关”也是后续理解二叉搜索树、二叉树的序列化与反序列化、路径问题等高级题目的基础。前序、中序、后序遍历是三种最常见的深度优先遍历DFS方式。初学时我们通常用递归几行代码轻松搞定但面试官总会追问“你能用迭代的方式写一下吗”许多人在递归解法游刃有余但一碰到栈模拟就捉襟见肘。其实递归与迭代本质上是一体两面递归隐式使用了系统调用栈迭代则是我们显式地模拟这个栈。本篇将带你从递归写法出发逐步推导出迭代写法并给出一个统一的迭代模板让不同遍历顺序的差异收敛为“访问顺序”的差异从而彻底告别死记硬背。核心概念递归的本质递归函数调用时编译器/解释器会将函数的局部变量、参数、返回地址等信息压入调用栈等到函数返回时再弹出。对于二叉树遍历每一次递归进入一个节点相当于“压栈”完成左右子树的遍历后返回相当于“弹栈”。正是这个隐式的栈维护了遍历的控制流。以中序遍历为例递归写法为void inorder(TreeNode root) { if (root null) return; inorder(root.left); System.out.print(root.val ); inorder(root.right); }这段代码的执行顺序是一直向左下钻直到左子树为空才处理当前节点再转向右子树。本质上就是“有左就入栈递归无左就出栈访问再处理右”。迭代思路用栈模拟递归迭代的关键是显式维护一个栈手动复现递归的入栈、出栈、访问时机。树的遍历有一个核心矛盾我们需要向下深入又需要在合适的时机回退并访问节点。栈帮助我们记住“回退点”。我们给出一个统一的迭代框架思路用一个指针 cur 表示当前遍历到的节点用一个栈记录待处理的祖先节点。循环条件是 cur ! null 或栈非空。不同的遍历顺序只是“访问节点”的时刻放在不同位置而已。实战示例下面我们以 Java 为例分别给出前序、中序、后序遍历的递归与迭代实现后序提供两种迭代方案最后提炼一个统一模板。所有代码可以直接复制运行。定义树节点结构public class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val x; } }1. 前序遍历 (根 - 左 - 右)递归写法public void preorderRec(TreeNode root) { if (root null) return; System.out.print(root.val ); // 先访问根 preorderRec(root.left); preorderRec(root.right); }迭代写法根左右前序是“到达节点即访问”所以可以用栈模拟先把右子节点压栈再把左子节点压栈保证左先出。public void preorderItr(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); // 左后入栈下次先弹出 } }这种方法是前序特供因为它利用了“访问即弹出”的特点无法直接套用到中序和后序。所以我们更需要一种全程用指针模拟递归过程的通用写法public void preorderItrGeneral(TreeNode root) { DequeTreeNode stack new ArrayDeque(); TreeNode cur root; while (cur ! null || !stack.isEmpty()) { while (cur ! null) { System.out.print(cur.val ); // 前序一路向左沿途访问 stack.push(cur); cur cur.left; } // 左子树到头了回退转向右子树 cur stack.pop(); cur cur.right; } }理解在不断向左深入的过程中立即访问当前节点并把自己压入栈为之后访问右子树做准备。当左为空弹出栈顶转向右子树循环往复。2. 中序遍历 (左 - 根 - 右)递归写法public void inorderRec(TreeNode root) { if (root null) return; inorderRec(root.left); System.out.print(root.val ); inorderRec(root.right); }迭代写法通用模板把前序通用的访问时机往下移一步从左子树返回时再访问。public void inorderItr(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; // 转向右子树 } }对比前序通用写法唯一区别是前序在入栈时就访问中序在出栈时才访问。这一模板充分体现了栈在递归回溯时的“记忆”能力。3. 后序遍历 (左 - 右 - 根)递归写法public void postorderRec(TreeNode root) { if (root null) return; postorderRec(root.left); postorderRec(root.right); System.out.print(root.val ); }后序遍历的迭代实现是三种遍历中最难的因为需要确保左右子树都处理完毕才能访问根。常见两种写法方法一双栈法前序变形后序遍历顺序是“左-右-根”前序是“根-左-右”。如果把前序左右互换变成“根-右-左”再反转就得到了“左-右-根”。可以用一个栈正常模拟“根右左”再用一个栈收集结果最后反转输出。public void postorderItrTwoStack(TreeNode root) { if (root null) return; DequeTreeNode stack new ArrayDeque(); DequeInteger result new ArrayDeque(); // 用作收集 stack.push(root); while (!stack.isEmpty()) { TreeNode node stack.pop(); result.push(node.val); // 插入结果栈相当于逆序收集 if (node.left ! null) stack.push(node.left); if (node.right ! null) stack.push(node.right); } // 输出结果栈即得到后序遍历 while (!result.isEmpty()) { System.out.print(result.pop() ); } }这种方法简单易懂但需要额外栈空间。方法二单栈 记录前驱通用迭代思路沿用中序的模板但需要判断是从左子树返回还是右子树返回只有当右子树已访问或为空时才能访问根节点。public void postorderItrSingleStack(TreeNode root) { 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) { cur cur.right; } else { // 右子树已空或已访问可以访问当前节点 System.out.print(cur.val ); stack.pop(); prev cur; // 记录访问过的节点 cur null; // 重要置空避免再次进入左子树循环 } } }这里的关键是prev指针它帮我们记住上一次访问的节点从而判断右子树是否刚刚处理完毕。当cur.right prev时说明右子树已经访问完可以安心访问根节点了。完整可运行示例下面整合以上所有方法并构建一棵示例树测试输出。import java.util.*; public class TreeTraversalDemo { 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.left new TreeNode(6); root.right.right new TreeNode(7); TreeTraversalDemo demo new TreeTraversalDemo(); System.out.print(前序递归: ); demo.preorderRec(root); System.out.println(); System.out.print(前序迭代: ); demo.preorderItrGeneral(root); System.out.println(); System.out.print(中序递归: ); demo.inorderRec(root); System.out.println(); System.out.print(中序迭代: ); demo.inorderItr(root); System.out.println(); System.out.print(后序递归: ); demo.postorderRec(root); System.out.println(); System.out.print(后序迭代双栈: ); demo.postorderItrTwoStack(root); System.out.println(); System.out.print(后序迭代单栈: ); demo.postorderItrSingleStack(root); System.out.println(); } // 节点定义 static class TreeNode { int val; TreeNode left, right; TreeNode(int x) { val x; } } // 递归方法 void preorderRec(TreeNode root) { if (root null) return; System.out.print(root.val ); preorderRec(root.left); preorderRec(root.right); } void inorderRec(TreeNode root) { if (root null) return; inorderRec(root.left); System.out.print(root.val ); inorderRec(root.right); } void postorderRec(TreeNode root) { if (root null) return; postorderRec(root.left); postorderRec(root.right); System.out.print(root.val ); } // 前序迭代通用 void preorderItrGeneral(TreeNode root) { DequeTreeNode stack new ArrayDeque(); TreeNode cur root; while (cur ! null || !stack.isEmpty()) { while (cur ! null) { System.out.print(cur.val ); stack.push(cur); cur cur.left; } cur stack.pop(); cur cur.right; } } // 中序迭代 void inorderItr(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; } } // 后序双栈 void postorderItrTwoStack(TreeNode root) { if (root null) return; DequeTreeNode stack new ArrayDeque(); DequeInteger result new ArrayDeque(); stack.push(root); while (!stack.isEmpty()) { TreeNode node stack.pop(); result.push(node.val); if (node.left ! null) stack.push(node.left); if (node.right ! null) stack.push(node.right); } while (!result.isEmpty()) System.out.print(result.pop() ); } // 后序单栈 void postorderItrSingleStack(TreeNode root) { 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) { cur cur.right; } else { System.out.print(cur.val ); stack.pop(); prev cur; cur null; } } } }运行输出针对树结构[1,2,3,4,5,6,7]前序递归: 1 2 4 5 3 6 7 前序迭代: 1 2 4 5 3 6 7 中序递归: 4 2 5 1 6 3 7 中序迭代: 4 2 5 1 6 3 7 后序递归: 4 5 2 6 7 3 1 后序迭代双栈: 4 5 2 6 7 3 1 后序迭代单栈: 4 5 2 6 7 3 1递归与迭代结果完全一致证明实现正确。常见问题/注意事项1. 为什么递归简单而迭代复杂递归是计算机自动管理函数调用栈我们只需关注“在何时做什么事”。迭代中我们需要自己控制栈的压入弹出还要处理指针的回退和转向逻辑更细致。理解递归时的隐藏栈行为就能轻松迁移到迭代。2. 三种遍历的统一模板真的存在吗是的。仔细观察三种迭代通用写法你会发现它们的骨架完全相同外层循环条件一样内层while(left)不断深入左子树。唯一的区别就是访问节点的位置- 前序在压栈之前深入沿途中访问。- 中序在左子树为空即将弹出栈顶时访问。- 后序在右子树处理完毕再次回到栈顶时访问需借助prev标记。这种模板将“遍历框架”与“业务逻辑访问”解耦非常高效。3. 后序单栈法中cur null是什么意思当访问完一个节点后将其指针置为null是为了确保下一轮循环不会再次进入while(cur ! null)让cur沿着左子树向下。因为此时栈顶的节点已经处理过左子树不允许再重复深入。置空后直接进入大循环处理下一个栈顶元素。4. 什么时候用哪种迭代写法面试或实际开发中前序/中序迭代尽量使用通用模板因为仅仅一个访问语句的位置差异方便记忆。后序如果图快可以双栈法如果强调空间则用单栈 prev。如果是做线索树Morris遍历那是另一个话题。5. 遇到非递归的变体题怎么办比如要求用迭代方式实现“求二叉树第k小的元素”利用中序、“迭代反转二叉树”等。核心仍是掌握通用模板在模板的关键节点加入你的处理逻辑甚至可以携带一个计数器、标志等因为模板本身就给了你一个线性化的遍历流。总结本文从递归的调用栈本质出发揭示了二叉树深度优先遍历的迭代实现原理。要点回顾-前序遍历通用模板中深度入栈时即访问节点-中序遍历在出栈的同时访问节点恰好符合左-根-右顺序-后序遍历利用双栈法前序变形反转或单栈前驱指针prev判断右子树是否完成。所有迭代写法都统一在一个框架中while (cur ! null || !stack.isEmpty()) 内部左深入循环。只要吃透这个框架面对各种二叉树的遍历变体题目便能以不变应万变。建议读者手动模拟一遍构建的样例树在纸上或用调试工具跟踪栈的变化彻底消化“递归隐式栈”与“迭代显式栈”的对应关系。掌握了这两种写法你就拥有了二叉树问题中最重要的基本功之一。