基于单栈与prev变量的二叉树后序遍历迭代代码逻辑解析

我完全理解你的困惑——单栈实现后序遍历的关键就在于prev变量，它就像我们遍历树时的「足迹」，帮我们判断当前节点的子节点是否已经处理完毕，从而确定什么时候可以把当前节点加入结果列表。

首先回忆下后序遍历的规则：左子树 → 右子树 → 根节点，迭代实现的难点在于，根节点必须等左右子树都遍历完才能被访问，而prev就是用来记录我们上一步访问的节点，以此判断当前节点的遍历阶段。

先把你的代码贴出来方便对照：

class BinaryTree {
    Node root;
    ArrayList<Integer> list = new ArrayList<Integer>();
    ArrayList<Integer> postOrderIterative(Node node) {
        Stack<Node> S = new Stack<Node>();
        if (node == null)
            return list;
        S.push(node);
        Node prev = null;
        while (!S.isEmpty()) {
            Node current = S.peek();
            if (prev == null || prev.left == current || prev.right == current) {
                if (current.left != null)
                    S.push(current.left);
                else if (current.right != null)
                    S.push(current.right);
                else {
                    S.pop();
                    list.add(current.data);
                }
            } else if (current.left == prev) {
                if (current.right != null)
                    S.push(current.right);
                else {
                    S.pop();
                    list.add(current.data);
                }
            } else if (current.right == prev) {
                S.pop();
                list.add(current.data);
            }
            prev = current;
        }
        return list;
    }
}

接下来逐个拆解核心条件分支：

1. 第一个条件：prev == null || prev.left == current || prev.right == current #

这个分支对应我们刚进入当前节点的场景：

• prev == null：第一次遍历，刚把根节点压入栈，这是我们访问的第一个节点
• prev.left == current 或 prev.right == current：我们是从父节点prev下来，刚到达子节点current
  此时我们需要遵循后序遍历的优先级，先处理左子树：
• 如果左子节点存在，就把左子节点压入栈，继续深入左子树
• 如果左子节点不存在但右子节点存在，就压入右子节点
• 如果左右子节点都不存在（当前是叶子节点），直接弹出节点并加入结果列表——因为叶子节点没有子树，直接满足「左→右→根」的顺序（它自己就是根）

2. 第二个条件：current.left == prev #

这个分支对应我们刚处理完当前节点的左子树的场景：

• prev是current的左孩子，说明左子树已经遍历完毕，现在要检查右子树：
  • 如果右子节点存在，就把右子节点压入栈，去遍历右子树
  • 如果右子节点不存在，说明左右子树都处理完了，弹出current并加入结果列表

3. 第三个条件：current.right == prev #

这个分支对应我们刚处理完当前节点的右子树的场景：

• prev是current的右孩子，说明左、右子树都已经遍历完毕，此时可以放心地弹出current并加入结果列表——这完全符合后序遍历「左→右→根」的顺序

最后一步：更新prev #

每次循环结束后，把prev设置为当前的current，这样下一次循环就能通过prev知道我们上一步的位置，进而判断当前节点处于哪个遍历阶段。

举个简单例子帮助理解 #

假设我们有一个二叉树：根(1) → 左(2)，根(1) → 右(3)
遍历过程：

1. 初始：栈压入1，prev=null
2. 第一次循环：current=1，满足第一个条件，压入2
3. 第二次循环：current=2，满足第一个条件，左右都为空，弹出2加入列表，prev=2
4. 第三次循环：current=1，此时prev=2（current.left == prev），检查右节点3存在，压入3
5. 第四次循环：current=3，满足第一个条件，左右都为空，弹出3加入列表，prev=3
6. 第五次循环：current=1，此时prev=3（current.right == prev），弹出1加入列表，prev=1
7. 栈空，结束，结果列表是[2,3,1]，完美符合后序遍历顺序

内容的提问来源于stack exchange，提问作者jonsnow