二叉树的中序遍历

给定一个二叉树的根节点 root ，返回它的中序遍历。

示例 1：

输入：root = [1,null,2,3] 输出：[1,3,2] 示例 2：

输入：root = [] 输出：[] 示例 3：

输入：root = [1] 输出：[1]

进阶做法：二叉树的中序遍历（Inorder Traversal）遵循“左子树 → 根节点 → 右子树”的顺序。以下是递归和迭代两种实现方法：

方法一：递归法

核心思路：
递归遍历左子树，访问根节点，再递归遍历右子树。

代码实现：

function inorderTraversal(root) {
    const result = [];
    
    function inorder(node) {
        if (!node) return;  // 终止条件：节点为空
        inorder(node.left); // 遍历左子树
        result.push(node.val); // 访问根节点
        inorder(node.right); // 遍历右子树
    }
    
    inorder(root);
    return result;
}

复杂度分析：

时间复杂度：O(n)，每个节点恰好访问一次。
空间复杂度：O(h)，递归栈深度为树的高度 h（最坏情况为 O(n)，树退化为链表）。

方法二：迭代法（使用栈）

核心思路：
借助栈模拟递归调用过程，优先遍历左子树，直到最左节点，然后访问根节点，再处理右子树。

步骤：

初始化栈：用于存储待访问的节点。
遍历左子树：从根节点开始，将所有左子节点压入栈，直到左子节点为空。
访问根节点：弹出栈顶节点，记录其值。
处理右子树：转向当前节点的右子树，重复步骤2和3。

代码实现：

function inorderTraversal(root) {
    const result = [];
    const stack = [];
    let current = root;
    
    while (current || stack.length > 0) {
        // 遍历左子树，将节点压入栈
        while (current) {
            stack.push(current);
            current = current.left;
        }
        
        // 访问根节点
        current = stack.pop();
        result.push(current.val);
        
        // 转向右子树
        current = current.right;
    }
    
    return result;
}

复杂度分析：

时间复杂度：O(n)，每个节点恰好访问一次。
空间复杂度：O(h)，栈深度为树的高度 h（最坏情况为 O(n)）。

示例验证

输入二叉树：

迭代法过程：

初始化：stack = []，current = 1。
遍历左子树：
- current = 1，压入栈，stack = [1]，转向左子节点（null）。
访问根节点：
- 弹出栈顶 1，记录 1，转向右子节点 2。
处理右子树：
- current = 2，压入栈，stack = [2]，转向左子节点 3。
- current = 3，压入栈，stack = [2, 3]，转向左子节点（null）。
- 弹出栈顶 3，记录 3，转向右子节点（null）。
- 弹出栈顶 2，记录 2，转向右子节点（null）。
结果：[1, 3, 2]，符合中序遍历顺序。

总结

递归法：简洁直观，适用于快速实现，但可能导致栈溢出。
迭代法：通过栈模拟递归过程，避免栈溢出，适合处理大规模数据。

方法一：递归法​

方法二：迭代法（使用栈）​

示例验证​

总结​

方法一：递归法

方法二：迭代法（使用栈）

示例验证

总结