如何用迭代（非递归）方式实现二叉树的前中后序遍历？

简化版

用一个显式栈模拟递归的调用栈。前序：弹出即访问，然后先压右孩子再压左孩子（保证左先出）。中序：一路把左孩子压栈到底，弹一个访问一个，再转向它的右孩子。后序：可以用「改造版前序（根右左）再反转结果」，或用一个标记记住节点是否第二次访问。迭代版能避免深树递归导致的栈溢出。

详细版

前序遍历（根左右）

List<Integer> preorder(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    if (root == null) return res;
    Deque<TreeNode> stack = new ArrayDeque<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        res.add(node.val);                        // 弹出即访问
        if (node.right != null) stack.push(node.right);  // 先压右
        if (node.left  != null) stack.push(node.left);   // 后压左 → 左先出
    }
    return res;
}

中序遍历（左根右）

List<Integer> inorder(TreeNode root) {
    List<Integer> res = 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();
        res.add(cur.val);                                        // 访问
        cur = cur.right;                                         // 转向右子树
    }
    return res;
}

后序遍历（左右根）

// 技巧：前序是「根左右」，把它改成「根右左」，最后整体反转 → 得到「左右根」
List<Integer> postorder(TreeNode root) {
    LinkedList<Integer> res = new LinkedList<>();
    if (root == null) return res;
    Deque<TreeNode> stack = new ArrayDeque<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        res.addFirst(node.val);                    // 头插，等于最后反转
        if (node.left  != null) stack.push(node.left);   // 注意先压左
        if (node.right != null) stack.push(node.right);  // 再压右 → 右先出
    }
    return res;
}

完整版教学

一、为什么要迭代版

递归遍历简洁，但每层递归占一个系统栈帧。当树很深（比如退化成链的树，高度 n 达几万几十万），递归会 StackOverflowError。迭代版用堆内存里的显式栈替代系统调用栈，空间大得多，能处理更深的树。原理上，迭代就是「手动做了递归时系统帮我们做的压栈/弹栈」。

二、前序最直观

前序是「根左右」，弹出即访问。关键是入栈顺序要和出栈顺序相反：我们希望左孩子先被处理，所以要后压左（栈后进先出，后压的先弹）。于是「先压右、后压左」，弹出顺序就是「根、左、右」。

三、中序的「一路向左」

中序是「左根右」，必须先把最左边的节点处理掉。所以用一个 cur 指针一路把左孩子压栈直到底，此时栈顶是最左节点；弹出访问它，再转向它的右子树，对右子树重复同样过程。这个「压左链 → 弹出访问 → 转右」的循环，正好产出「左根右」的顺序。

四、后序的两种思路

后序「左右根」最麻烦，因为根要等左右都处理完才访问。两种常见解法：

改造前序 + 反转（推荐好记）：前序是「根左右」。如果把前序的左右压栈顺序对调，得到「根右左」；再把整个结果反转，就变成「左右根」= 后序。代码只需在前序基础上改两行 + 用头插。
单栈 + 标记法：用一个变量记录「上一个被访问的节点」，只有当一个节点的右孩子为空或已被访问过，才访问该节点，否则先处理右子树。逻辑严谨但代码稍长。

五、和层序遍历区分

前中后序（DFS）用栈（LIFO）。
层序（BFS）用队列（FIFO）。

把「栈换成队列」不会得到某种 DFS，而是变成 BFS——数据结构的选择直接决定了遍历的形态。这是理解树遍历的关键。

六、常见误区与追问

遍历	栈中保存的核心信息	出结果的时机
前序	待访问节点	节点出栈时立刻输出
中序	向左走过的祖先链	左边走到底后回退输出
后序	节点及其孩子是否处理完	左右都处理完后输出

记忆钩子：递归版靠系统调用栈保存现场；迭代版只是把这个现场显式放进自己维护的栈里。

误区：三种 DFS 迭代写法只改输出位置就行。 递归里可以这么理解，但迭代时中序和后序需要额外保存「走到哪了」「右子树是否处理过」。
误区：前序压栈时先压左再压右。 栈是后进先出，想先访问左子树，应先压右孩子再压左孩子。
误区：中序遍历适合所有树都得到有序结果。 只有二叉搜索树的中序遍历才天然有序，普通二叉树没有这个性质。
误区：后序一定只能用反转前序结果。 反转法常见且好写，也可以用 prev 指针记录上一次访问节点，模拟真正的左右根。
追问：迭代版空间复杂度是多少？ DFS 栈空间是 O(h)，退化链表为 O(n)；层序 BFS 队列空间与最大层宽有关。
追问：为什么面试常问迭代遍历？ 它能验证你是否理解递归调用栈的本质，而不是只会背递归模板。

八、伪代码与不变量

数据结构题最好把操作过程写成伪代码，因为指针、索引或状态变化一旦说不清，就容易在边界用例上出错。以如何用迭代（非递归）方式实现二叉树的前中后序遍历？为例，可以先固定不变量，再解释每一步为什么保持它。

初始化：维护结构不变量 invariant
遍历/调整：每处理 1 个节点或元素，都只改变必要指针/索引
校验：操作后结构仍满足顺序、连通性或堆/树性质
复杂度：每个元素最多进入/离开结构 O(1) 或 O(log n) 次

九、一步步推演与边界

回答如何用迭代（非递归）方式实现二叉树的前中后序遍历？时，最好额外走一遍小样例。先用 3～5 个元素演示正常操作，再故意加入空结构、单元素、重复值或极端位置，观察不变量是否仍成立。比如链表题要盯住前驱、当前、后继 3 个指针；树题要说明递归返回值代表什么；堆题要说明上浮/下沉什么时候停止；图题要说明 visited 或入度数组何时更新。

这种推演的价值在于把“我知道算法”变成“我能证明边界也不会错”。很多面试失分不是主流程不会，而是少了空节点、尾节点、重复边、环、K 越界这类边界。把这些点主动讲出来，既能减少代码 bug，也能让复杂度分析更可信。

边界类型	检查方式	容易出错的地方
空结构	输入为空或 root/head 为 null	直接访问属性导致异常
单元素	只有 1 个节点或元素	前驱/后继、左右子树判断错误
重复值	多个元素相等	比较条件写成 < 还是 <=
极端位置	头尾、最大最小、第一层最后一层	更新指针或索引越界

补充边界演练

为了把如何用迭代（非递归）方式实现二叉树的前中后序遍历？真正讲透，可以再补一组边界演练。第一组是空结构或空输入，用来确认代码不会在访问 head、root、stack top 或队首时崩溃；第二组是单元素，用来确认循环条件不会多走一步；第三组是 2～3 个元素的最小非平凡样例，用来观察指针、栈、队列或 visited 状态如何变化。

如果是树遍历题，就画出 root、left、right 三个节点，逐步记录栈里元素的进出；如果是图遍历题，就用 4 个点、4 条边验证 BFS 的层次性和 DFS 的路径性；如果是链表题，就把 pre、cur、next 三个指针写在纸上，每移动一次都检查链是否断开。面试时把这个过程讲出来，比单纯写出最终代码更能说明你真的理解结构变化。

边界 1：空输入 -> 直接返回，不访问节点属性
边界 2：单元素 -> 循环最多处理 1 次，结果保持合法
边界 3：三个元素 -> 手动跟踪每一步状态变化
验证目标：不变量始终成立，且每个节点/元素被处理次数可解释

补充栈状态时间线

迭代遍历最容易错的地方，是只记住“用栈”但说不清栈里保存的到底是什么。以一棵 3 个节点的树为例：根节点 A，左子节点 B，右子节点 C。前序遍历希望输出 A, B, C，所以可以先弹出 A，再按“右后左先”的顺序把 C、B 入栈；这样下一次弹出的就是 B。

初始：stack = [A]
弹 A：output = [A]，push C，再 push B，stack = [C, B]
弹 B：output = [A, B]，stack = [C]
弹 C：output = [A, B, C]，stack = []

中序遍历的栈含义又不一样：它保存的是“已经沿左链走过，但还没输出的祖先节点”。因此循环里通常有两个动作：先一路向左压栈，直到空；再弹出栈顶输出，并转向右子树。这个过程等价于递归里的“先访问左子树，再访问根，再访问右子树”，只是把系统调用栈换成了手写栈。

后序遍历最需要解释“为什么不能简单根左右”。一种常见写法是先做“根右左”，最后反转得到“左右根”；另一种写法是用 lastVisited 标记上一次访问的节点，判断右子树是否已经处理完。面试时如果能把这两种栈语义说清楚，基本就不会被追问卡住。

遍历方式	栈里保存什么	关键动作	易错点
前序	待访问节点	弹出即输出，先压右再压左	入栈顺序写反
中序	左链祖先节点	先压到最左，再弹出输出	忘记转向右子树
后序	待确认的根节点或根右左序列	等左右子树完成后输出根	右子树未处理就提前输出

还可以把递归栈和显式栈一一对应起来看：

递归函数的参数，相当于显式栈里的节点对象。
递归返回的位置，相当于循环里“弹栈后继续处理”的位置。
递归里的左右子树调用顺序，相当于显式栈里的压栈顺序。
递归的最大调用深度是树高 h，显式栈的最大容量通常也是 O(h)。
退化成链表时，h = n，所以两者最坏空间都会变成 O(n)。

七、加强记忆

迭代遍历用显式栈替代递归调用栈（防深树栈溢出）。前序：弹出即访问，先压右后压左；中序：一路压左到底、弹出访问、再转右；后序：把前序改成「根右左」再反转（或单栈+标记）。记住 DFS 用栈、BFS 用队列——换数据结构就换了遍历形态。

简化版

详细版