迭代式中序遍历：无需递归的二叉树遍历算法

在本篇文章中，我们将探讨如何使用迭代的方法来实现二叉树的中序遍历。

通常情况下，我们学习树的第一种遍历方式是递归，因为它非常直观且易于实现。然而，在处理大型数据结构或在系统栈空间有限的环境下，递归可能会导致栈溢出。为了解决这一问题，我们可以使用迭代方法，即利用显式的栈结构来模拟递归过程。

为什么选择迭代？

在我们深入代码之前，让我们先了解一下为什么需要掌握这种技能：

• 空间效率优化：虽然最坏情况下空间复杂度仍为 O(h)，其中 h 是树的高度，但迭代法让我们能更精细地控制栈的使用。
• 面试常备：这是技术面试中非常基础且高频的算法题目。
• 理解树的结构：手动管理栈的过程能加深我们对树遍历逻辑的理解。

算法核心思路

中序遍历的顺序是：左子树 -> 根节点 -> 右子树。

在递归方法中，系统调用栈自动帮我们保存了路径。而在迭代方法中，我们需要自己维护这个路径。我们的策略如下：

• 我们从根节点开始。
• 我们将当前节点初始化为根节点。
• 只要当前节点不为空，或者栈不为空，我们就继续循环。
• 第一步：深入左侧。只要当前节点存在，我们就将其压入栈中，并移动到其左孩子。这一步的目的就是为了找到最底层的左节点（即中序遍历的起始点）。
• 第二步：处理节点。当当前节点变为空时，说明已经到了最左边。此时我们从栈顶弹出一个元素。这个节点就是我们当前需要处理的节点，我们将其值存入结果列表。
• 第三步：转向右侧。处理完当前节点后，我们将当前节点移动到其右孩子，准备重复上述过程。

图解演示

让我们想象一棵简单的二叉树：

    1
   / \
  2   3
 /
4

• 初始化：当前节点为 1，栈为空。
• 入栈：1 入栈 -> 2 入栈 -> 4 入栈。当前节点变为 4 的左孩子。
• 出栈并访问：当前节点为空。栈顶弹出 4。访问 4。当前节点变为 4 的右孩子（空）。
• 继续出栈：栈顶弹出 2。访问 2。当前节点变为 2 的右孩子（空）。
• 继续出栈：栈顶弹出 1。访问 1。当前节点变为 1 的右孩子（3）。
• 右侧子树：3 入栈。3 没有左孩子。弹出 3 并访问。
• 结束：栈为空，当前节点为空。

结果：[4, 2, 1, 3]

代码实现

以下是使用 C++、Java、Python、C# 和 JavaScript 的具体实现代码。

#### C++ 代码

#include 
using namespace std;

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

// 迭代式中序遍历函数
vector inOrderTraversal(struct Node* root) {
    stack st;
    Node* curr = root;
    vector result;
    
    // 当当前节点不为空或栈不为空时，继续循环
    while (curr != NULL || !st.empty()) {
        
        // 步骤 1：深入到最左侧的节点
        while (curr != NULL) {
            st.push(curr);
            curr = curr->left;
        }
        
        // 当前节点一定为 NULL
        curr = st.top();
        st.pop();
        
        // 步骤 2：处理当前节点
        result.push_back(curr->data);
        
        // 步骤 3：访问右子树
        curr = curr->right;
    }
    return result;
}

// 主函数用于测试
int main() {
    /* 构建如下的树
          1
        /   \
       2     3
      / \
     4   5
    */
    struct 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);

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

#### Java 代码

import java.util.ArrayList;
import java.util.Stack;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

class Solution {
    // 迭代式中序遍历
    public ArrayList inOrderTraversal(TreeNode root) {
        Stack stack = new Stack();
        ArrayList result = new ArrayList();
        TreeNode curr = root;

        while (curr != null || !stack.isEmpty()) {
            // 深入到最左侧
            while (curr != null) {
                stack.push(curr);
                curr = curr.left;
            }

            // 弹出栈顶元素
            curr = stack.pop();
            result.add(curr.val);

            // 转向右子树
            curr = curr.right;
        }
        return result;
    }
}

#### Python 代码

# 定义二叉树节点
class Node:
    def __init__(self, val):
        self.data = val
        self.left = None
        self.right = None

def in_order_traversal(root):
    current = root
    stack = []
    result = []
    
    while True:
        # 如果当前节点存在，压入栈并向左走
        if current is not None:
            stack.append(current)
            current = current.left
        # 如果当前节点为空，但栈不为空
        elif stack:
            current = stack.pop()
            result.append(current.data)
            # 处理右子树
            current = current.right
        else:
            break
    return result

# 测试代码
if __name__ == "__main__":
    root = Node(1)
    root.left = Node(2)
    root.right = Node(3)
    root.left.left = Node(4)
    root.left.right = Node(5)
    
    print("中序遍历结果:", in_order_traversal(root))

#### C# 代码

using System;
using System.Collections.Generic;

// 定义节点类
public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int x) { val = x; }
}

public class Solution {
    public IList InorderTraversal(TreeNode root) {
        IList result = new List();
        Stack stack = new Stack();
        TreeNode curr = root;
        
        while (curr != null || stack.Count > 0) {
            // 遍历至最左节点
            while (curr != null) {
                stack.Push(curr);
                curr = curr.left;
            }
            
            curr = stack.Pop();
            result.Add(curr.val);
            
            curr = curr.right;
        }
        
        return result;
    }
}

#### JavaScript 代码

// 定义二叉树节点
class TreeNode {
    constructor(val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var inorderTraversal = function(root) {
    const stack = [];
    const result = [];
    let curr = root;
    
    while (curr !== null || stack.length > 0) {
        while (curr !== null) {
            stack.push(curr);
            curr = curr.left;
        }
        
        curr = stack.pop();
        result.push(curr.val);
        
        curr = curr.right;
    }
    
    return result;
};

复杂度分析

让我们来分析一下这种算法的效率。

• 时间复杂度：O(n)。其中 n 是二叉树中的节点数量。在遍历过程中，每个节点都会被压入栈一次并被弹出栈一次。
• 空间复杂度：O(h)。其中 h 是树的高度。空间消耗主要来自于栈。在最坏的情况下（树退化成链表），空间复杂度为 O(n)；在平衡树的情况下，空间复杂度为 O(log n)。

总结

通过这篇文章，我们掌握了如何使用栈这一工具，将递归的思维方式转化为迭代的代码实现。这种“显式栈”的技巧不仅仅适用于中序遍历，同样可以套用到前序遍历和后序遍历中。希望大家在理解原理的基础上，多动手练习，彻底掌握这一算法。

我们将在后续的内容中继续探索更多数据结构与算法的奥秘。