如何设计一个二叉搜索树迭代器？

简化版

BST 迭代器要按升序不断返回下一个元素，本质是“可暂停的中序遍历”。用一个栈保存尚未访问的祖先路径：初始化时把根到最左节点一路压栈；next() 弹出栈顶作为答案，再把它的右子树一路压左；hasNext() 判断栈是否为空。

详细版

因为 BST 的中序遍历结果是升序，所以迭代器只要模拟中序遍历即可。普通中序遍历会一次性遍历完整棵树；迭代器要求每次调用 next() 只前进一步，因此不能提前把所有节点放进数组，否则空间是 O(n)，也不符合“懒加载”的思想。

更好的做法是维护一个单调访问栈。栈里保存“下一批可能被访问的节点”，栈顶永远是当前还没输出的最小节点。初始化时 pushLeft(root)；每次 next() 弹出一个节点 node，如果它有右子树，就对 node.right 执行 pushLeft，保证下一个最小节点又回到栈顶。单次 next() 的均摊时间 O(1)，最坏一次可能 O(h)，空间 O(h)。

完整版教学

一、为什么这题不是简单中序遍历

如果题目只问“输出 BST 升序序列”，直接中序遍历即可。但迭代器多了两个接口：next() 和 hasNext()。这意味着遍历过程要能暂停、恢复，并且每次只交付一个值。把所有节点提前放进数组当然也能过功能，但它把初始化变成 O(n)，空间也是 O(n)，当树有 100000 个节点而用户只调用 3 次 next() 时，前面 99997 个节点的遍历都浪费了。

普通中序遍历：一次性跑完 root -> list
BSTIterator：每次 next 只推进到下一个节点

这类题的面试重点是“懒遍历”。你要证明自己知道 BST 的中序有序，也知道如何用栈保存遍历现场，而不是把结果数组当成唯一方案。

二、栈里到底保存什么

栈里保存的是“从当前子树一路向左走的路径”。初始化时，把 root, root.left, root.left.left... 压入栈，直到空。因为 BST 中最小值一定在最左边，所以栈顶就是第一个要返回的节点。

        7
       / \
      3   15
         /  \
        9    20

初始化 pushLeft(7):
push 7, push 3
stack top -> 3

当弹出 3 后，3 没有右子树，下一个就是栈里的 7。当弹出 7 后，7 有右子树 15，不能直接返回 15，因为 15 的左边还有 9，所以要对 15 执行 pushLeft，压入 15、9，栈顶变成 9。

三、用数字序列模拟几次 next

用上面的树，迭代器输出应该是 3, 7, 9, 15, 20。栈的变化如下：

操作	返回值	栈变化说明	栈顶
初始化	-	压入 7、3	3
`next()`	3	弹出 3，无右子树	7
`next()`	7	弹出 7，对右子树 15 压左：15、9	9
`next()`	9	弹出 9，无右子树	15
`next()`	15	弹出 15，对右子树 20 压左：20	20
`next()`	20	弹出 20，无右子树	空

这个过程说明一个关键点：栈顶永远是“尚未输出的最小节点”。只要这个不变量成立，next() 弹栈返回就是正确的。

四、标准代码写法

实现时最好抽一个私有方法 pushLeft，这样构造函数和 next() 都能复用，代码更不容易写乱。

class BSTIterator {
    private Deque<TreeNode> stack = new ArrayDeque<>();

    public BSTIterator(TreeNode root) {
        pushLeft(root);
    }

    public int next() {
        TreeNode node = stack.pop();
        if (node.right != null) {
            pushLeft(node.right);
        }
        return node.val;
    }

    public boolean hasNext() {
        return !stack.isEmpty();
    }

    private void pushLeft(TreeNode node) {
        while (node != null) {
            stack.push(node);
            node = node.left;
        }
    }
}

next() 默认在题目约束下调用前一定有下一个元素；真实工程里可以在栈空时抛异常。面试题里不必过度设计异常处理，重点是遍历状态维护。

五、为什么说 next 均摊 O(1)

单看某一次 next()，它可能弹出一个节点后又沿右子树压入一条左链，最坏 O(h)。但从整棵树生命周期看，每个节点只会被压栈一次、弹栈一次，所以 n 次 next() 总成本是 O(n)。平均到每次，就是均摊 O(1)。

总压栈次数 = n
总弹栈次数 = n
n 次 next 的总操作数约 2n
均摊成本 = O(1)

空间复杂度是 O(h)，因为栈里最多保存一条从根到叶子的路径。平衡 BST 中 h 约为 log2(n)，例如 n=1023 时高度约 10；如果退化成链表，h 可能等于 n。

六、常见误区与追问

记忆钩子：BSTIterator 不是存答案数组，而是存“中序遍历走到一半的现场”。

误区：初始化时把整棵树中序遍历进数组最简单，所以就是最优。 数组法功能正确，但空间 O(n)，且失去懒加载优势。
误区：弹出节点后直接把右孩子压栈即可。 右子树里最小的节点在右孩子的最左链上，必须 pushLeft(node.right)。
误区：hasNext() 要继续搜索树。 搜索状态已经保存在栈里，判断栈是否为空即可。
追问：为什么 next() 是均摊 O(1)？ 因为每个节点整个生命周期只进栈一次、出栈一次，n 次调用总成本 O(n)。
追问：能不能支持 prev()？ 可以，但需要额外维护双向迭代状态，或改成双栈/缓存已访问节点，空间和逻辑都会增加。
追问：如果树会动态插入删除怎么办？ 这版迭代器默认树结构不变；动态修改会破坏栈中路径，需要并发修改检测或重新设计。

七、加强记忆

BST 迭代器就是把中序遍历拆成很多次 next() 调用：构造时压根到最左路径，保证栈顶是最小未访问节点；每次弹出栈顶后，如果它有右子树，就把右子树的最左路径压进去，保证下一个栈顶仍然是最小未访问节点。面试回答要强调三个点：不提前展开数组、栈保存遍历现场、每个节点只压弹一次，所以空间 O(h)，next() 均摊 O(1)。

简化版

详细版