173. 二叉搜索树迭代器

📚思路一：提前中序遍历 + 列表缓存

核心逻辑

本解法采用 提前中序遍历 的策略：

在构造函数中，使用递归对 BST 进行一次完整的中序遍历，将所有节点值按升序保存到 List<Integer> 中。
维护一个索引变量 index，初始化为 -1。
next() 方法：将 index 加 1，并返回列表中对应位置的元素。
hasNext() 方法：判断 index 是否小于列表的最后一个位置（index < list.size() - 1）。

代码实现

class BSTIterator {
    private List<Integer> list;
    private int index;
    
    public BSTIterator(TreeNode root) {
        list = new ArrayList<>();
        index = -1;
        inorder(root);
    }
    
    // 中序遍历
    private void inorder(TreeNode root) {
        if (root == null) return;
        inorder(root.left);
        list.add(root.val);
        inorder(root.right);
    }
    
    public int next() {
        index++;
        return list.get(index);
    }
    
    public boolean hasNext() {
        return index < list.size() - 1;
    }
}

时间复杂度：
- 构造函数：O(N)，其中 N 是 BST 的节点总数，需要一次完整的中序遍历。
- next()：O(1)，直接访问数组。
- hasNext()：O(1)，直接比较索引。
空间复杂度： O(N)，需要存储所有节点的值到列表中。

📚思路二：栈模拟中序遍历（迭代器模式)

核心逻辑

采用栈模拟中序遍历的策略，实现真正的迭代器（按需生成）：

维护一个 Deque 作为栈
在构造函数中，调用辅助方法 BSTIteratorHelper，将从根节点开始沿左子树一直走到最左叶子节点的所有节点压入栈中。
next() 方法：
- 从栈顶弹出当前节点 t。
- 返回 t.val。
- 如果 t 有右孩子，则调用 BSTIteratorHelper(t.right) 将右子树的左链全部压入栈。
hasNext() 方法：直接检查栈是否为空。

代码实现

class BSTIterator {
    private Deque<TreeNode> stack;
    
    public BSTIterator(TreeNode root) {
        stack = new ArrayDeque<>();
        pushLeftBranch(root);
    }
    
    // 将左链全部压入栈
    private void pushLeftBranch(TreeNode node) {
        while (node != null) {
            stack.push(node);
            node = node.left;
        }
    }
    
    public int next() {
        TreeNode top = stack.pop();
        // 如果弹出节点有右子树，将其右子树的左链压入栈
        if (top.right != null) {
            pushLeftBranch(top.right);
        }
        return top.val;
    }
    
    public boolean hasNext() {
        return !stack.isEmpty();
    }
}

时间复杂度：
- 构造函数：O(H)，H 为树的高度（将左链压入栈）。
- 平均 next()：O(1)，均摊时间复杂度（每个节点进栈一次，出栈一次）。
- hasNext()：O(1)，直接检查栈是否为空。
空间复杂度： O(H)，H 为树的高度，栈中最多存储 H 个节点（当前左链的长度）。

自我总结🚀

方法一：数组预存法

核心思想

构造函数里一次性遍历整棵树，把中序结果存进数组，之后直接取。

项目	详情
构造函数	O(n)：中序遍历整棵树，存进 `List`
`next()`	O(1)：直接取数组下标
`hasNext()`	O(1)：比较下标
空间复杂度	O(n)：存了所有节点
是否满足进阶要求	❌ 不满足（空间要求 O(h)，但你的用了 O(n)）
优点	💖 代码极其简单，思路直白，适合第一次实现
缺点	🧠 如果树特别大（比如 100 万个节点），内存直接爆了

方法二：栈迭代法（进阶解法）

核心思想

不存全部，只存“当前左边界路径”，边走边取。

项目	详情
构造函数	O(h)：仅压入根节点及其所有左孩子（h 是树高）
`next()`	均摊 O(1)（最坏 O(h)，但平均常数）：出栈取数据
`hasNext()`	O(1)：看栈是否为空
空间复杂度	O(h)：栈里最多放树高个节点
是否满足进阶要求	✅ 完美满足（O(h) 内存 + 均摊 O(1)）
优点	💾 内存占用小，适合处理大数据量、流式输入
缺点	🧠 逻辑稍绕，需要理解栈手动模拟递归的思想