深入解析：利用栈在 Java 中实现二叉树的非递归遍历

作为开发者，我们在处理二叉树时，递归方法通常是最直观、最容易上手的选择。递归代码简洁优雅，但你是否曾想过，在极端情况下，过深的树结构会导致栈溢出？或者在面试中，面试官要求你用空间复杂度更低的方式实现遍历？这时，掌握利用栈来实现非递归遍历就显得尤为重要。

在这篇文章中，我们将深入探讨如何使用 栈 这一经典的数据结构，在 Java 中手动实现二叉树的三种深度优先遍历：中序、前序和后序。我们将摒弃简单的代码罗列，而是像两个工程师在白板前讨论一样，剖析每一步的逻辑，分享实战中的最佳实践，并揭示这些算法背后的运行机制。准备好你的 Java 环境，让我们一起开始这场探索之旅。

为什么我们需要栈？

在开始编码之前，让我们先统一一下认识。线性数据结构（如数组、链表）的遍历是一目了然的，从头走到尾即可。但二叉树是一种分层的数据结构，遍历它涉及到“选择方向”——向左走还是向右走？

当我们使用递归时，编译器在底层默默地帮我们维护了一个调用栈。每当我们进入一个新节点，当前的“现场”（比如变量值、执行位置）就会被压入栈中；当我们返回时，现场从栈中弹出。非递归遍历的本质，其实就是接管这个控制权，自己显式地维护这个栈，从而决定访问节点的顺序。

准备工作：定义节点结构

为了方便后续的演示，我们将使用一个标准的二叉树节点类。为了代码的整洁和线程安全，我们通常会将节点属性定义为 final（如果不需要修改引用），但在演示算法的灵活性上，我们保持经典的定义。

在所有接下来的例子中，我们都将使用这棵示例树作为输入：

      1
    /   \
   2     3
  / \
 4   5

这棵树的遍历结果如下，你可以用它们来验证我们代码的正确性：

• 中序: 4 2 5 1 3
• 前序: 1 2 4 5 3
• 后序: 4 5 2 3 1

A. 中序遍历：左 -> 根 -> 右

中序遍历是最基础的非递归遍历，也是理解“栈如何模拟递归”的最佳切入点。它的核心思想是：一路向左，走到黑，然后回头，再向右。

#### 算法思路解析

让我们手动模拟一下这个过程：

• 初始化： 我们从根节点（1）开始。因为中序遍历是“左-根-右”，我们不能急着打印 1。我们需要先找到 1 的最左边。
• 入栈： 我们将 1 压入栈，然后移动到 2；将 2 压入栈，移动到 4；将 4 压入栈，移动到 null。此时栈里是 [1, 2, 4]。
• 出栈与处理： 此时当前节点为 null，说明左边走到头了。我们从栈顶弹出一个元素（4），打印它。这就是我们要找的第一个节点。
• 转向右子树： 处理完 4 后，根据中序逻辑，我们应该去 4 的右子树。对于 4 来说，右子树为空，所以我们继续弹出栈顶元素（2），打印 2。然后转向 2 的右子树（5）。
• 循环往复： 重复上述过程，直到栈为空且当前节点也为空。

#### Java 代码实现

下面是经过优化的 Java 实现，包含了详细的中文注释。

import java.util.Stack;

// 二叉树节点定义
class Node {
    int data;
    Node left, right;

    public Node(int item) {
        data = item;
        left = right = null;
    }
}

// 用于演示中序遍历的类
class BinaryTreeInorder {
    Node root;

    void inorder() {
        // 如果根节点为空，直接返回
        if (root == null)
            return;

        // 创建一个栈来保存路径上的节点
        Stack stack = new Stack();
        Node curr = root;

        // 只有当当前节点不为空 或者 栈不为空时，循环才继续
        // 这里是关键：如果 curr 为空，说明左路走完，需要从栈里取；如果栈空，说明所有节点处理完
        while (curr != null || stack.size() > 0) {

            // 第一阶段：一路向左走，并将沿途节点压栈
            while (curr != null) {
                // 在访问左子树之前，先将当前节点压栈保存
                // 这样我们稍后可以“回来”处理它（打印它或访问它的右子树）
                stack.push(curr);
                curr = curr.left;
            }

            // 第二阶段：此时 curr 一定为 null，说明到达了最左端
            // 弹出栈顶元素，这是我们目前需要处理的节点
            curr = stack.pop();

            // 打印节点数据 (中序遍历的“根”部分)
            System.out.print(curr.data + " ");

            // 第三阶段：转向右子树
            // 这一步之后，curr 可能为 null（右子树不存在），也可能有值
            // 如果有值，在下次外层循环开始时，它会被压入栈并继续向左探索
            curr = curr.right;
        }
    }

    public static void main(String args[]) {
        BinaryTreeInorder tree = new BinaryTreeInorder();
        // 构建示例树
        tree.root = new Node(1);
        tree.root.left = new Node(2);
        tree.root.right = new Node(3);
        tree.root.left.left = new Node(4);
        tree.root.left.right = new Node(5);

        System.out.println("中序遍历结果:");
        tree.inorder();
    }
}

输出：

中序遍历结果:
4 2 5 1 3 

B. 前序遍历：根 -> 左 -> 右

前序遍历的逻辑略有不同。我们需要在处理左子树之前就先访问（打印）节点本身。这意味着我们不需要像中序遍历那样先走到最左边再打印，而是在遇到节点的第一面就处理它。

#### 方法一：使用栈的标准解法

这种方法与前文中序遍历的结构非常相似。区别在于：在将节点压入栈之后，我们立即打印它。剩下的流程依然是一路向左，没路了再从栈里弹出，去右边找。

import java.util.Stack;

class BinaryTreePreorder {
    Node root;

    void preorder() {
        if (root == null)
            return;

        Stack stack = new Stack();
        Node curr = root;

        // 当栈不为空或当前节点不为空时继续
        while (curr != null || stack.size() > 0) {
            
            // 向左遍历
            while (curr != null) {
                // 重点：前序遍历是“根”在前
                // 所以我们在压栈的同时直接打印当前节点
                System.out.print(curr.data + " ");
                
                stack.push(curr);
                curr = curr.left;
            }

            // 左边走到头了，弹出栈顶元素
            curr = stack.pop();

            // 准备处理右子树
            curr = curr.right;
        }
    }

    public static void main(String args[]) {
        BinaryTreePreorder tree = new BinaryTreePreorder();
        tree.root = new Node(1);
        tree.root.left = new Node(2);
        tree.root.right = new Node(3);
        tree.root.left.left = new Node(4);
        tree.root.left.right = new Node(5);

        System.out.println("前序遍历结果:");
        tree.preorder();
    }
}

#### 方法二：更直观的“先右后左”入栈法

除了模仿递归的写法，前序遍历还有一种非常符合人类直觉的写法。利用栈“后进先出”的特性：我们要先处理左孩子，再处理右孩子，那么我们可以先把右孩子压入栈，再把左孩子压入栈。这样出栈的时候，左孩子就会先出来。

这种方法的循环结构更简单，也不需要内部的 while(curr != null) 循环。

import java.util.Stack;

class BinaryTreePreorderAlternative {
    Node root;

    void preorder() {
        if (root == null)
            return;

        Stack stack = new Stack();
        // 先把根节点压入栈
        stack.push(root);

        while (stack.empty() == false) {
            
            // 弹出栈顶元素并打印
            Node curr = stack.pop();
            System.out.print(curr.data + " ");

            // 压入右孩子（因为我们要先处理左，所以让右先入栈垫底）
            if (curr.right != null) {
                stack.push(curr.right);
            }
            
            // 压入左孩子（最后入栈，最先出栈）
            if (curr.left != null) {
                stack.push(curr.left);
            }
        }
    }
}

C. 后序遍历：左 -> 右 -> 根

后序遍历是非递归算法中的“大魔王”。为什么？因为当我们从栈顶弹出一个节点时，我们无法确定它是应该被打印了，还是仅仅是因为我们要去访问它的右子树。

• 中序遍历中，弹出意味着左子树处理完了，打印当前，然后去右边。
• 后序遍历中，弹出意味着左子树处理完了，但我们还没处理右子树，所以不能打印。我们必须先去右边，等右边回来后，才能打印当前节点。

#### 核心难点与解决方案

如何解决“该打印还是该去右边”的问题？我们需要一个标记来记录上一次访问的节点。

如果我们要处理的节点的右孩子，恰好等于上一次访问过的节点，那就说明右子树已经处理完了，现在可以放心大胆地打印当前节点了。

#### Java 代码实现

下面的实现非常高效，只用了一个 prev 指针来追踪上一步的状态。

import java.util.Stack;

class BinaryTreePostorder {
    Node root;

    void postorder() {
        if (root == null)
            return;

        Stack stack = new Stack();
        Node curr = root;
        
        // 这里的逻辑稍微抽象一些，我们采用一种通用的遍历框架
        // 只要栈不为空，就继续循环
        while (curr != null || !stack.isEmpty()) {
            
            // 第一步：同样是一路向左走，并沿途压栈
            if (curr != null) {
                stack.push(curr);
                curr = curr.left;
            } else {
                // 第二步：左边走到头了，查看栈顶元素（注意，是 peek，不是 pop）
                Node temp = stack.peek().right;
                
                // 情况 A：如果栈顶元素的右孩子为空，或者我们已经访问过右孩子了
                if (temp == null || temp == curr) { 
                    // 这里利用了 curr 作为 prev 指针的逻辑，但在本例中我们优化一下逻辑
                    // 重新构建一个更清晰的逻辑版本在下面
                }
            }
        }
    }
    // 为了保证清晰度，我们使用一种包含 prev 指针的完整实现版本
}

为了让你能彻底理解，我们采用最清晰的双指针法实现（INLINECODEb3d8f1ae 和 INLINECODEde900e0a）：

import java.util.Stack;

class BinaryTreePostorderClean {
    Node root;

    void postorder() {
        if (root == null) return;

        Stack stack = new Stack();
        Node current = root;
        Node prev = null; // 记录上一个访问过的节点

        stack.push(root);

        while (!stack.isEmpty()) {
            current = stack.peek(); // 看一眼栈顶，不急着拿下来

            // 如果我们要处理的节点是叶子节点，或者它的子节点已经被访问过了
            if (prev == null || prev.left == current || prev.right == current) {
                // 如果有左孩子，先处理左孩子（压栈以便下次循环处理）
                if (current.left != null) {
                    stack.push(current.left);
                } 
                // 如果没有左孩子但有右孩子，处理右孩子
                else if (current.right != null) {
                    stack.push(current.right);
                } 
                // 如果是叶子节点，左右都没有，那就直接打印并弹出
                else {
                    System.out.print(current.data + " ");
                    stack.pop();
                }
            } 
            // 如果当前节点的左子树刚刚被处理完 (prev 是左孩子)
            else if (current.left == prev) {
                // 现在应该去右子树了
                if (current.right != null) {
                    stack.push(current.right);
                } 
                // 没有右子树，说明该节点处理完毕，打印并弹出
                else {
                    System.out.print(current.data + " ");
                    stack.pop();
                }
            } 
            // 如果当前节点的右子树刚刚被处理完 (prev 是右孩子)
            else if (current.right == prev) {
                // 说明左右子树都搞定了，现在轮到根节点了
                System.out.print(current.data + " ");
                stack.pop();
            }

            // 更新 prev 指针，记录我们刚刚处理过的节点
            prev = current;
        }
    }

    public static void main(String args[]) {
        BinaryTreePostorderClean tree = new BinaryTreePostorderClean();
        tree.root = new Node(1);
        tree.root.left = new Node(2);
        tree.root.right = new Node(3);
        tree.root.left.left = new Node(4);
        tree.root.left.right = new Node(5);

        System.out.println("后序遍历结果:");
        tree.postorder();
    }
}

复杂度分析与最佳实践

在这三种遍历方式中，我们都可以总结出以下特点：

• 时间复杂度：O(n)。我们每个节点大约都被访问了 2 到 3 次（入栈一次、出栈一次、检查关系），这依然是线性的。
• 空间复杂度：O(h)，其中 h 是树的高度。栈的深度取决于树的形态。最坏情况下（树退化为链表），栈深为 n；最好情况下（平衡树），栈深为 log n。

#### 实战建议

• 面试时首选中序和前序： 这两种写法逻辑清晰，不容易出错。如果面试官问后序，你可以先写出前序，然后解释后序的难点在于判断左右子树是否都已处理。
• 使用 ArrayDeque 代替 Stack： 虽然 INLINECODE50d22705 是历史遗留类，但在现代 Java 开发中，我们通常建议使用 INLINECODE464ea41a，因为它继承自 Vector，具有同步开销，效率较低。Deque 的 INLINECODE77813480 和 INLINECODE16017d96 方法完全兼容栈的操作。
• Morris 遍历： 如果你需要在 O(1) 空间复杂度下完成遍历（不使用栈），你可以去了解一下 Morris Traversal，它通过修改树的结构（临时将右子树指向父节点）来实现回溯。不过在生产代码中修改树结构需要格外小心。

总结

通过这篇文章，我们不仅实现了代码，更重要的是理解了栈是如何接管递归的控制流的。从一路向左的中序遍历，到利用栈“后进先出”特性反转顺序的前序遍历，再到需要记录“上一步”状态的后序遍历，每一步都加深了我们对二叉树结构的理解。

希望下次当你面对二叉树问题时，除了递归，你也能自信地拿起栈这个工具，写出优雅且高效的迭代解法。如果你有任何疑问，或者想分享你的见解，欢迎随时交流。