二叉树的中序遍历：递归与迭代实现详解 | 二叉树遍历指南

二叉树的中序遍历（In-order Traversal）是一种深度优先遍历方法，遍历顺序为：左子树 -> 根节点 -> 右子树。中序遍历常用于二叉搜索树（BST）中，可以得到一个有序的节点值序列。

递归实现

递归实现是最直观的方式，代码简洁易懂。

function inorderTraversal(root) {
    const result = [];
    
    function traverse(node) {
        if (node === null) return;
        
        // 遍历左子树
        traverse(node.left);
        
        // 访问根节点
        result.push(node.val);
        
        // 遍历右子树
        traverse(node.right);
    }
    
    traverse(root);
    return result;
}

迭代实现

迭代实现使用栈来模拟递归过程，避免了递归的栈溢出问题。

function inorderTraversal(root) {
    const result = [];
    const stack = [];
    let current = root;
    
    while (current !== null || stack.length > 0) {
        // 遍历到最左节点
        while (current !== null) {
            stack.push(current);
            current = current.left;
        }
        
        // 访问节点
        current = stack.pop();
        result.push(current.val);
        
        // 遍历右子树
        current = current.right;
    }
    
    return result;
}

示例

假设有如下二叉树：

    1
     \
      2
     /
    3

中序遍历结果为：[1, 3, 2]

复杂度分析

• 时间复杂度：O(n)，其中 n 是二叉树的节点数。每个节点恰好被访问一次。
• 空间复杂度：O(h)，其中 h 是二叉树的高度。递归栈的深度取决于树的高度，最坏情况下为 O(n)。

应用场景

中序遍历在以下场景中非常有用：

1. 二叉搜索树：中序遍历可以得到一个有序的节点值序列。
2. 表达式树：中序遍历可以生成中缀表达式。

总结

中序遍历是二叉树遍历的基础操作之一，掌握其递归和迭代实现对于理解树结构和解决相关问题非常重要。在实际开发中，根据具体需求选择合适的实现方式。