LeetCode BST 迭代器：中序遍历迭代器设计 O(h) 空间

题目要求

实现二叉搜索树迭代器，支持 next() 返回下一个最小值，hasNext() 判断是否有下一个。要求均摊 O(1) 时间，O(h) 空间（h 为树高）。

核心思路：中序遍历惰性展开

BST 中序遍历即升序序列。用栈模拟递归，仅保存当前路径节点（≤ h 个）。

两版实现对比

版本 1：预先遍历全树（空间 O(n)，不合格）

public class BSTIterator {
    private Deque deque = new ArrayDeque<>();
    public BSTIterator(TreeNode root) { inorder(root); }
    private void inorder(TreeNode root) {
        Stack st = new Stack<>();
        TreeNode p = root;
        while (p != null || !st.empty()) {
            if (p != null) { st.push(p); p = p.left; }
            else { p = st.pop(); deque.add(p); p = p.right; }
        }
    }
    public boolean hasNext() { return !deque.isEmpty(); }
    public int next() { return hasNext() ? deque.poll().val : -1; }
}

版本 2：惰性展开（空间 O(h)，合格）

public class BSTIterator {
    private Stack stack = new Stack<>();
    public BSTIterator(TreeNode root) {
        pushLeft(root);
    }
    private void pushLeft(TreeNode node) {
        while (node != null) { stack.push(node); node = node.left; }
    }
    public boolean hasNext() { return !stack.empty(); }
    public int next() {
        TreeNode node = stack.pop();
        if (node.right != null) pushLeft(node.right);
        return node.val;
    }
}

关键点解析

1. 构造函数：仅将根节点及其左链压栈
2. next()：弹出栈顶（当前最小），若有右子树，压入右子树的左链
3. 均摊 O(1)：每个节点进栈出栈各一次，总操作 2n，平均 O(1)
4. 空间 O(h)：栈中始终保存从根到当前节点的路径 + 待访问右子树的左链

C++ 版本

class BSTIterator {
    stack st;
    void pushLeft(TreeNode* node) {
        while (node) { st.push(node); node = node->left; }
    }
public:
    BSTIterator(TreeNode* root) { pushLeft(root); }
    bool hasNext() { return !st.empty(); }
    int next() {
        TreeNode* node = st.top(); st.pop();
        if (node->right) pushLeft(node->right);
        return node->val;
    }
};

扩展：PeekingIterator / 泛化

同理可实现二叉树前序/后序迭代器，或任意树的 DFS 迭代器。核心模式：栈保存「待访问节点及其状态」。