深入解析：如何在不使用递归的情况下实现二叉树的中序遍历

作为一名开发者，当我们处理二叉树遍历问题时，最先想到的往往是递归。代码简洁、逻辑直观，但递归并非没有代价。函数调用的栈空间消耗、在某些嵌入式环境中对栈溢出的担忧，以及我们有时希望对遍历过程有更精细的控制，这些都促使我们探索非递归的解决方案。

在这篇文章中，我们将深入探讨如何在不使用递归的情况下对二叉树进行中序遍历。我们将从最基础的栈模拟法开始，一步步拆解其背后的逻辑，并最终探讨一种更为高阶的 Morris 遍历算法，它能在不使用额外栈空间的情况下完成任务。让我们开始吧！

核心挑战：为什么要避开递归？

在正式进入代码之前，让我们先明确一下目标。中序遍历的顺序是 “左 -> 根 -> 右”。递归之所以优雅，是因为编译器帮我们维护了一个调用栈，自动记录了“回溯”的路径。当我们决定放弃递归时，这个责任就转移到了我们肩上：我们需要手动管理这个状态。

这通常意味着我们需要使用一个显式的数据结构——栈，或者巧妙地修改树的结构来记录状态。

方法一：使用栈模拟递归过程

这是最直观的非递归解法。我们的核心思路是：显式地使用栈来保存我们在访问左子树路径上经过的每一个节点，以便在左子树处理完后能找回根节点并访问右子树。

#### 算法逻辑详解

让我们把遍历过程分解为几个关键步骤：

• 初始化：创建一个空的栈 INLINECODEa8c70924，并将当前指针 INLINECODE6ad88e3a 指向根节点。
• 一路向左：从当前节点开始，只要它不是空的，我们就把它压入栈中，然后移动到它的左子节点。这一步会一直持续，直到我们走到树的最左边。此时，栈顶存放的就是我们要访问的第一个节点（也就是中序遍历中的第一个节点）。
• 弹出与访问：当 curr 为空时，说明我们走到了尽头。这时，我们从栈中弹出一个节点（这是最近一次压入的未访问节点），打印或存储它的值。
• 转向右侧：访问完当前节点（即刚才弹出的节点）后，根据中序遍历规则，接下来应该处理它的右子树。因此，我们将 curr 指向刚才弹出节点的右子节点，并重复上述过程。
• 循环终止条件：当 curr 为空（无路可走）且栈也为空（所有路径都已回溯完毕）时，遍历结束。

#### 实战图解

为了让你更清楚地看到这个过程，让我们以下面的二叉树为例进行手动推演：

示例树结构：

       1
     /   \
    2     3
   / \
  4   5

步骤推演：

• 初始化：栈 INLINECODE20f067f6，INLINECODEea9ff631。

• 节点 1：将 1 压入栈。INLINECODEcb3e86b2。INLINECODE00c59179 移动到左子节点 2。
• 节点 2：将 2 压入栈。INLINECODE3ebfebd3。INLINECODE28bca8cf 移动到左子节点 4。
• 节点 4：将 4 压入栈。INLINECODE25b418aa。INLINECODE5e23bb29 移动到左子节点（为空）。
• 回溯节点 4：INLINECODE5ac214b9 为空。从栈弹出 4。INLINECODEa79a0a68。输出：4。curr 移动到节点 4 的右子节点（为空）。
• 回溯节点 2：INLINECODE252a750e 仍为空。从栈弹出 2。INLINECODE69eb5835。输出：2。curr 移动到节点 2 的右子节点 5。
• 节点 5：将 5 压入栈。INLINECODEbed83bb6。INLINECODE9f3b8985 移动到左子节点（为空）。
• 回溯节点 5：INLINECODEe06bcd59 为空。从栈弹出 5。INLINECODE6cda603b。输出：5。curr 移动到节点 5 的右子节点（为空）。
• 回溯节点 1：INLINECODE666aeaca 为空。从栈弹出 1。INLINECODEb36bc569。输出：1。curr 移动到节点 1 的右子节点 3。
• 节点 3：将 3 压入栈。INLINECODE5d411c55。INLINECODEef3779e1 移动到左子节点（为空）。
• 回溯节点 3：INLINECODEe6c73b55 为空。从栈弹出 3。INLINECODEd747e391。输出：3。curr 移动到节点 3 的右子节点（为空）。

最终结果： 4 2 5 1 3

#### 代码实现：C++

让我们看看这段逻辑如何转化为简洁的 C++ 代码。

#include 
#include 
#include 
using namespace std;

// 定义树节点结构
struct Node {
    int data;
    Node* left;
    Node* right;
    
    // 构造函数
    Node(int val) {
        data = val;
        left = nullptr;
        right = nullptr;
    }
};

// 主函数：非递归中序遍历
vector inOrderTraversal(Node* root) {
    vector result; // 用于存储遍历结果
    stack s;     // 辅助栈
    Node* curr = root;  // 当前指针
    
    // 当当前节点不为空 或 栈不为空时，继续遍历
    while (curr != nullptr || !s.empty()) {
        
        // 第一阶段：一路向左，将沿途节点压入栈
        while (curr != nullptr) {
            s.push(curr);
            curr = curr->left;
        }
        
        // 第二阶段：当前节点为空，说明到达最左端
        // 弹出栈顶元素（即当前要处理的节点）
        curr = s.top();
        s.pop();
        
        // 将节点值加入结果集
        result.push_back(curr->data);
        
        // 第三阶段：转向右子树
        // 如果右子树为空，curr 在下一次循环中会触发再次出栈
        curr = curr->right;
    }
    
    return result;
}

// 辅助函数：创建测试用例
int main() {
    /* 构建如下的二叉树
          1
        /   \
       2     3
      / \
     4   5 
    */
    Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);

    cout << "中序遍历结果: ";
    vector res = inOrderTraversal(root);
    for (int val : res) {
        cout << val << " ";
    }
    cout << endl;

    return 0;
}

#### 代码解析与易错点

• 内层循环的作用：注意那个 while (curr != nullptr) 循环。它的作用是“探路”。只要当前节点还有左孩子，我们就一直把父节点存起来，向左走。这保证了栈顶永远是我们要处理的下一个节点。
• 外层循环的判断：必须同时检查 INLINECODE9eecd2d5 和 INLINECODE422575e4。当从栈中弹出一个节点并处理完后，我们将 INLINECODE6a2dae88 设为它的右孩子。此时 INLINECODEb02a0835 可能非空（如果有右子树），也可能为空（如果是叶子节点）。如果为空且栈也空了，说明整个树遍历完毕。
• 时间与空间复杂度：

* 时间：O(n)。每个节点都被压入栈一次，弹出一次，且只访问一次。

* 空间：O(h)，其中 h 是树的高度。这是栈所需要的最大空间。在最坏情况下（树退化为链表），空间复杂度为 O(n)。

方法二：进阶之路 – Morris 遍历算法

如果你在面试中回答出了上面的栈方法，面试官通常会非常满意。但如果你能提到 Morris 遍历，那绝对是加分项。

#### 思考：能不能不用栈？

前面的方法中，栈占据了 O(h) 的空间。我们能不能利用树本身的空闲指针来记录回溯路径呢？这就是 Morris 遍历的核心思想。

#### 算法核心：线索二叉树

Morris 遍历通过修改树的结构，在遍历过程中临时建立“线索”。具体来说，当我们在处理当前节点 curr 时：

• 如果 INLINECODEa32b99b5 没有左孩子，这意味着它就是当前子树里最“左”的节点。我们可以直接打印 INLINECODE5a4f587f，然后进入右子树。
• 如果 INLINECODE0eeaf3ec 有左孩子，我们需要找到左子树中的最右节点（即中序遍历中 INLINECODEbd0c9ee6 的前驱节点），我们称之为 predecessor。
• 关键的一步：我们将 INLINECODEd28d64d8 的右指针（原本是空的）临时指向 INLINECODEcda0b5a5。这就建立了一个回路。

* 当我们从 INLINECODE5f25b632 向左走到 INLINECODEbb031bdb 并处理完后，通过这个临时建立的右指针，我们可以直接回到 curr，而不需要栈。

* 当我们第二次回到 INLINECODEd69036b0 时，说明左子树已经遍历完毕。此时我们将 INLINECODE84a4cb98 的右指针恢复为 INLINECODEd094b030（恢复树的原始结构），打印 INLINECODEfaabc2f2，然后前往右子树。

#### 图解 Morris 遍历

让我们看上面的例子：节点 1。

• curr = 1。左孩子是 2。找到 2 的最右节点（即 5）。
• 修改 5 -> right = 1。现在树中多了一条线：5 指向 1。
• curr 移动到 2。
• … 处理 2 (左孩子 4) …
• 当 INLINECODEe2a0f5ee 再次回到 1 时（通过 5 的右指针），程序检测到 INLINECODE55e666f6。这意味着左子树遍历完了。于是断开 INLINECODE84bb68e5，打印 1，INLINECODE9a276b75 移动到 3。

这种方法不需要额外的栈空间，空间复杂度仅为 O(1)。

#### 代码实现：C++ (Morris Traversal)

#include 
#include 
using namespace std;

struct Node {
    int data;
    Node* left;
    Node* right;
    Node(int val) : data(val), left(nullptr), right(nullptr) {}
};

vector morrisInOrder(Node* root) {
    vector result;
    Node* curr = root;
    
    while (curr != nullptr) {
        if (curr->left == nullptr) {
            // 情况 1：没有左子树，直接处理当前节点
            result.push_back(curr->data);
            curr = curr->right;
        } else {
            // 情况 2：有左子树，找到前驱节点
            Node* pre = curr->left;
            while (pre->right != nullptr && pre->right != curr) {
                pre = pre->right;
            }
            
            if (pre->right == nullptr) {
                // 第一次访问到前驱节点，建立线索
                pre->right = curr;
                curr = curr->left;
            } else {
                // 第二次回到这里，说明线索已建立，说明左子树已处理完
                pre->right = nullptr; // 恢复树结构
                result.push_back(curr->data);
                curr = curr->right;
            }
        }
    }
    return result;
}

int main() {
    Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);

    cout << "Morris 中序遍历结果: ";
    vector res = morrisInOrder(root);
    for (int val : res) {
        cout << val << " ";
    }
    cout << endl;

    return 0;
}

总结与最佳实践

在这篇文章中，我们解锁了二叉树中序遍历的两种非递归写法。你可能会问，在实际开发中我该怎么选？

• 首选栈模拟法：代码逻辑清晰，易于维护和调试。虽然空间复杂度是 O(h)，但在大多数应用场景下，树的高度并不会造成内存溢出。除非你对空间有极致的要求，否则这是最稳妥的选择。
• 了解 Morris 遍历：如果你正在进行底层库开发，或者树的结构极其巨大（比如深度达数百万级），Morris 遍历的 O(1) 空间优势将无可替代。此外，它也是理解高级树结构的敲门砖。

#### 常见错误提醒

• 死循环：在 Morris 遍历中，判断 INLINECODEbb1ba7d3 非常关键。如果忘记这个判断，就会在 INLINECODE5d9364e9 和 INLINECODE8a4027f2 之间无限循环。切记处理完节点后要断开线索 (INLINECODE7468f3cf)。
• 栈的判空：在使用栈的方法中，外层 INLINECODE5da276a4 循环的条件必须是 INLINECODE36b0b629。很多人会漏掉 s.empty() 的检查，导致树还未遍历完就退出了。

希望这篇文章能帮助你彻底理解非递归遍历的本质。不要只停留在看懂代码，建议你自己打开 IDE，动手敲一遍这两种算法，观察指针的每一次跳转。祝你编码愉快！