🔗 二叉树的中序遍历

题目来源：94. 二叉树的中序遍历 – 力扣（LeetCode）

📌 题目描述

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

中序遍历的访问顺序为：左子树 → 根节点 → 右子树。

✅ 示例说明

示例 1：

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

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

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

⚠️ 提示

• 节点数范围：[0, 100]
• 节点值范围：[-100, 100]

💡 解法：栈模拟递归（迭代法）

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        LinkedList<TreeNode> stack = new LinkedList<>();
        TreeNode curr = root;

        while (curr != null || !stack.isEmpty()) {
            if (curr != null) {
                stack.push(curr);
                curr = curr.left;
            } else {
                TreeNode node = stack.pop();
                list.add(node.val);
                curr = node.right;
            }
        }

        return list;
    }
}

📊 复杂度分析

• 时间复杂度：O(n)
  每个节点恰好被访问一次。
• 空间复杂度：O(h)
  h 为树的高度，最坏情况（链状树）为 O(n)，平均为 O(log n)。

🧩 解题思路

中序遍历天然适合递归，但题目常要求不使用递归（考察栈的运用能力）。

迭代核心思想：

1. 一路向左：从当前节点出发，不断将左子节点压入栈，直到为空。
2. 访问栈顶：弹出栈顶节点（即当前最左的未访问节点），加入结果。
3. 转向右子树：将当前指针指向该节点的右子树，重复上述过程。

整个过程模拟了递归调用栈的行为：

• 压栈 = 递归进入左子树
• 弹栈 = 回溯并访问根
• 转右 = 递归处理右子树