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

简化版

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

详细版

前序遍历（根左右）

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 队列空间与最大层宽有关。
追问：为什么面试常问迭代遍历？ 它能验证你是否理解递归调用栈的本质，而不是只会背递归模板。

七、加强记忆

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

简化版

详细版