二叉树的统一迭代法

算法-二叉树的统一迭代法

背景

• 算法–二叉树的统一迭代法

• 博主以代码随想录算法公开课进行学习

题目

• 二叉树的统一迭代法（前中后序）

思路

• 这种方法的核心是：用 null 作为 “标记”，区分「已访问但未处理」和「可直接处理」的节点：
  • 未标记节点（非 null）：仅 “访问” 节点，不处理（不加入结果集），按遍历顺序将「子节点 + 标记 null + 当前节点」重新入栈；
  • 标记节点（遇到 null）：说明栈顶下一个节点是 “可处理节点”，弹出 null 后，取出节点并加入结果集。
  • 类比：
    • 非 null 节点：拿到快递包裹（仅签收，未拆包），先把包裹放一边，去取后续包裹；
    • null 标记：拆包提醒，看到这个标记，就回去拆之前签收的包裹（加入结果集）。

代码实现

import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

// 二叉树节点定义
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;
    }
}

class Solution {
    // ==================== 前序遍历（统一标记法）：中-左-右 ====================
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new LinkedList<>();
        Stack<TreeNode> st = new Stack<>();
        if (root != null) st.push(root); // 根节点非空则入栈

        while (!st.empty()) {
            TreeNode node = st.peek(); // 查看栈顶节点（不弹出）
            if (node != null) {
                st.pop(); // 弹出当前节点，避免重复处理

                // 前序遍历：中-左-右 → 栈是后进先出，入栈顺序需为「右-左-中」
                if (node.right != null) st.push(node.right); // 1. 入栈右节点（后处理）
                if (node.left != null) st.push(node.left);   // 2. 入栈左节点（中间处理）
                st.push(node);                               // 3. 入栈中节点（先处理）
                st.push(null); // 标记：中节点已访问，未处理

            } else { // 遇到 null 标记，处理栈顶节点
                st.pop(); // 弹出 null 标记
                node = st.peek(); // 取出待处理的节点
                st.pop();
                result.add(node.val); // 加入结果集
            }
        }
        return result;
    }

    // ==================== 中序遍历（统一标记法）：左-中-右 ====================
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new LinkedList<>();
        Stack<TreeNode> st = new Stack<>();
        if (root != null) st.push(root);

        while (!st.empty()) {
            TreeNode node = st.peek();
            if (node != null) {
                st.pop(); // 弹出当前节点，避免重复处理

                // 中序遍历：左-中-右 → 入栈顺序需为「右-中-左」
                if (node.right != null) st.push(node.right); // 1. 入栈右节点（后处理）
                st.push(node);                               // 2. 入栈中节点（中间处理）
                st.push(null); // 标记：中节点已访问，未处理
                if (node.left != null) st.push(node.left);   // 3. 入栈左节点（先处理）

            } else { // 处理标记节点
                st.pop();
                node = st.peek();
                st.pop();
                result.add(node.val);
            }
        }
        return result;
    }

    // ==================== 后序遍历（统一标记法）：左-右-中 ====================
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new LinkedList<>();
        Stack<TreeNode> st = new Stack<>();
        if (root != null) st.push(root);

        while (!st.empty()) {
            TreeNode node = st.peek();
            if (node != null) {
                st.pop(); // 弹出当前节点，避免重复处理

                // 后序遍历：左-右-中 → 入栈顺序需为「中-右-左」
                st.push(node);                               // 1. 入栈中节点（后处理）
                st.push(null); // 标记：中节点已访问，未处理
                if (node.right != null) st.push(node.right); // 2. 入栈右节点（中间处理）
                if (node.left != null) st.push(node.left);   // 3. 入栈左节点（先处理）

            } else { // 处理标记节点
                st.pop();
                node = st.peek();
                st.pop();
                result.add(node.val);
            }
        }
        return result;
    }

    // 测试案例
    public static void main(String[] args) {
        // 构建二叉树：
        //      1
        //       \
        //        2
        //       /
        //      3
        TreeNode root = new TreeNode(1);
        root.right = new TreeNode(2);
        root.right.left = new TreeNode(3);

        Solution solution = new Solution();
        System.out.println("前序遍历：" + solution.preorderTraversal(root)); // [1,2,3]
        System.out.println("中序遍历：" + solution.inorderTraversal(root)); // [1,3,2]
        System.out.println("后序遍历：" + solution.postorderTraversal(root)); // [3,2,1]
    }
}

核心规律：入栈顺序与遍历顺序的关系

• 这种统一标记法的唯一差异就是「非 null 节点的入栈顺序」，记住以下规律即可通杀前 / 中 / 后序：

遍历顺序	目标顺序	栈入栈顺序（非 null 节点）	核心调整点
前序	中 - 左 - 右	右 - 左 - 中	先压右 → 再压左 → 最后压中 + 标记
中序	左 - 中 - 右	右 - 中 - 左	先压右 → 再压中 + 标记 → 最后压左
后序	左 - 右 - 中	中 - 右 - 左	先压中 + 标记 → 再压右 → 最后压左

注意事项

• 空节点不入栈：if (node.right != null) 等判断必须加，避免栈中混入 null（除了手动加的标记）；
• 先 pop 再入栈：处理非 null 节点时，必须先 st.pop() 弹出当前节点，否则会重复循环处理；
• 标记位置：null 标记必须紧跟在 “中节点” 之后入栈，标记该节点 “已访问未处理”；
• LinkedList 效率更高：结果集用 LinkedList 而非 ArrayList，因为频繁 add 操作时 LinkedList 效率更高（无需扩容）。

总结

• 统一标记法的核心是用 null 标记 “已访问未处理” 的节点，处理逻辑完全通用；
• 前 / 中 / 后序的唯一差异是「非 null 节点的入栈顺序」，记住 “目标顺序逆序入栈” 的核心规律；
• 这种方法代码复用性极强，学会后可快速适配任意二叉树遍历场景，是迭代遍历的 “万能模板”。