二叉树遍历：四种方式的递归与迭代模板

一句话结论（30s）

前/中/后序遍历的区别只是「访问根节点的时机」（根在前/中/后），递归就改一行 visit(root) 的位置；因为栈是 FILO，迭代版前序要先压右再压左、中序一路向左、后序用 prev 标记右子树是否访问过，层序则用队列加 size 分层。

核心原理（2min）

递归：前序根→左→右，中序左→根→右，后序左→右→根，三者只差 visit(root) 的位置。
前序迭代：栈先右后左入栈，pop 时左先弹出（FILO）。为什么必须”先右后左”入栈？ 因为栈是后进先出，想让左子树先被访问，就必须让左子树后入栈——这是把递归的手动压栈”翻译”成显式栈时的第一道坎。
中序迭代：一路向左入栈，弹栈访问后转右子树。
后序迭代：prev 标记，cur.right == null || cur.right == prev 时才访问根。
层序：队列 + 每轮 size 分层，一轮 for 循环处理一整层。

底层深入（5-10min）

递归模板（一行）

void preorder(TreeNode root) {
    if (root == null) return;
    visit(root);            // 前序：先访问根
    preorder(root.left);
    preorder(root.right);
}

void inorder(TreeNode root) {
    if (root == null) return;
    inorder(root.left);
    visit(root);            // 中序：中间访问根
    inorder(root.right);
}

void postorder(TreeNode root) {
    if (root == null) return;
    postorder(root.left);
    postorder(root.right);
    visit(root);            // 后序：最后访问根
}

三种遍历的区别只是 visit(root) 的位置——前中后 = 根在前/中/后位置。

💭 思考：看到”遍历二叉树”怎么一秒写出递归？——别背三份代码，只记一条：前/中/后序的差别仅仅在”根”何时被访问。前序=根在左右之前，中序=根夹在左右之间，后序=根在左右之后。所以先写固定框架”递归左、递归右”，再把 visit(root) 插到对应位置——三份模板就变成”移动一行”的事。

前序迭代（栈）

void preorderIter(TreeNode root) {
    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        visit(node);
        if (node.right != null) stack.push(node.right);  // 先右后左！
        if (node.left != null) stack.push(node.left);
    }
}

栈弹出顺序 = FILO。要让左子树先访问，必须先压右再压左——pop 时左先弹出。

中序迭代（栈 + 一路向左）

void inorderIter(TreeNode root) {
    Stack<TreeNode> stack = new Stack<>();
    TreeNode cur = root;
    while (cur != null || !stack.isEmpty()) {
        while (cur != null) {
            stack.push(cur);        // 一路向左
            cur = cur.left;
        }
        cur = stack.pop();          // 栈顶是最左节点
        visit(cur);                 // 访问
        cur = cur.right;            // 转向右子树
    }
}

核心：先走到最左，弹栈访问，转向右子树。对右子树重复同样的”一路向左”。

💭 思考：中序迭代为什么要”一路向左压栈”？——中序要求”左→根→右”，所以必须先把整条左链压进栈，弹栈时栈顶自然是最左（也是最先该访问）的节点；访问完它，它的右子树又按同样规则处理。这是把递归的”先深入左子树再回退”用显式栈复刻出来——凡是递归先走左的遍历，迭代都逃不开”一路向左”这个动作。

后序迭代（栈 + prev 标记）

void postorderIter(TreeNode root) {
    Stack<TreeNode> stack = new Stack<>();
    TreeNode cur = root, 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) {
            visit(cur);        // 右子树已访问或为空 → 访问根
            prev = stack.pop();
            cur = null;
        } else {
            cur = cur.right;   // 转向右子树
        }
    }
}

后序需要等到右子树也访问完才访问根。prev 标记上一个访问的节点——如果 cur.right == prev 说明右子树刚被访问过了。为什么后序是三种遍历里最难的？ 因为前序/中序访问完节点就”用完”了，而后序访问根之前必须确认右子树也处理完——所以需要一个 prev 额外记录”上一次访问的是谁”，用 cur.right == prev 判断右子树是否刚被回访过，否则会重复入栈死循环。

层序（BFS 队列）

List<List<Integer>> levelOrder(TreeNode root) {
    Queue<TreeNode> q = new LinkedList<>();
    q.offer(root);
    while (!q.isEmpty()) {
        int size = q.size();
        List<Integer> level = new ArrayList<>();
        for (int i = 0; i < size; i++) {
            TreeNode n = q.poll();
            level.add(n.val);
            if (n.left != null) q.offer(n.left);
            if (n.right != null) q.offer(n.right);
        }
        result.add(level);
    }
    return result;
}

用 size 区分每层——每一轮 for 循环处理的是一整层。

💭 思考：层序为什么用队列而不是栈？——层序要的是”同一层从左到右、先入先出”，队列 FIFO 天然满足；栈 LIFO 会先弹最后入栈的右节点，顺序全乱。更深一层：栈对应”深度优先”（一路往下），队列对应”宽度优先”（一层铺开），选对容器其实就是在选遍历的”方向”。

总结

遍历	递归	迭代
前序	根→左→右	栈 + 先右后左入栈
中序	左→根→右	栈 + 一路向左
后序	左→右→根	栈 + prev 标记
层序	—	队列 + size 分层

章末提问

前中后序遍历的区别到底在哪？ 结论：区别只在”访问根节点的时机”——前序根在前、中序根在中、后序根在后；递归实现里就是移动一行 visit(root) 的位置，其余左右子树顺序不变。
中序遍历的迭代版为什么能不用 prev，后序却必须用？ 结论：因为中序弹出节点后直接转右子树、节点不会再回来，不需要知道右子树状态；而后序必须在”右子树访问完”之后才访问根，得用 prev 标记上一个访问节点来判定右子树是否已经处理。
层序遍历为什么用队列而不是栈？ 结论：因为层序要求”同一层从左到右按先进先出的顺序输出”，队列的 FIFO 恰好符合；换成栈的 LIFO 就会先弹最近入栈的右节点，顺序全乱。

二叉树遍历——前序、中序、后序、层序的递归与迭代模板