二叉搜索树迭代器 图解题解

这道题到底在问什么

树

[7,3,15,null,null,9,20]

next 序列

3 → 7 → 9 → 15 → 20

要求

next/hasNext 均摊 O(1),内存 O(h)

先想最直接的笨办法

铺垫：BST 中序遍历就是升序；笨办法全存数组要 O(n)，目标是只用 O(h)、靠一个存「最左路径」的栈。下面一步步演给你看。（动画第 3 步）

最优解：一步一步想明白

1. 3铺垫：BST 中序遍历就是升序；笨办法全存数组要 O(n)，目标是只用 O(h)、靠一个存「最左路径」的栈。下面一步步演给你看。
2. 4中序遍历就是「一直往左走到底,这个最左节点就是当下最小的」。我们把这条往左走的路径压进栈,栈顶永远是下一个该输出的最小值。
3. 5弹出栈顶后,它的左边早走完了,接下来该轮到它的右子树里最小的——所以对右孩子再来一次「往左到底」。下面用真树演一遍。
4. 6中序(升序)= 3,7,9,15,20盯住两样东西:左下这棵树里高亮的节点,和右侧栈的内容。栈顶画在最上面——它就是「下一个要吐出来的数」。
5. 7指针停在根 7初始化做一件事:pushLeft(根)。指针先落在根 7 上,准备沿左边一路压栈。
6. 8压入 7,继续往左把 7 压栈。7 有左孩子 3,所以还没到底,指针移到 3,继续往左。
7. 9压入 3,3 无左孩子 → 停再把 3 压栈。3 没有左孩子,「往左到底」结束。此刻栈顶 3 就是整棵树最小的数——初始化完成。
8. 10输出 3;3 无右孩子调 next():弹出栈顶 3 作为返回值。检查 3 有没有右孩子——没有,所以不用补任何东西。新栈顶变成 7。
9. 11已输出:33 已经吐出(变灰)。栈里只剩 7,它就是下一个最小。
10. 12输出 7;7 有右孩子 15再调 next():弹出 7。这次 7 有右孩子 15——7 左边和它自己都处理完了,接下来轮到右子树里最小的,所以对 15 做 pushLeft。
11. 13指针落到 15,准备 pushLeft指针移到 7 的右孩子 15。现在对它「往左到底」,把这条新的最左链补进栈。
12. 14压入 15,继续往左从右孩子 15 起再「往左到底」:先压 15。15 有左孩子 9,还没到底。
13. 15压入 9,9 无左孩子 → 停再压 9,9 没有左孩子,停。栈变成 [15, 9],栈顶 9 是当前最小。这一次 next() 返回的是刚弹出的 7。
14. 16已输出:3, 7输出序列到了 3, 7。栈里现在是 15(底)、9(顶),下一个该吐 9。
15. 17输出 9;9 无右孩子next():弹出栈顶 9。9 没有右孩子,不补。新栈顶回到 15。
16. 18已输出:3, 7, 99 吐出。栈里只剩 15,它是下一个最小。
17. 19输出 15;15 有右孩子 20next():弹出 15。15 有右孩子 20,对 20 做 pushLeft。
18. 20压入 20,20 无左孩子 → 停从 20 往左:压 20,20 没有左孩子,立刻到底。栈现在只有一个 20。本次 next() 返回的是刚弹出的 15。
19. 21已输出:3, 7, 9, 15输出到 3, 7, 9, 15。只剩栈顶 20 没吐了。
20. 22输出 20;20 无右孩子,栈空最后一次 next():弹出 20,它没有右孩子,栈彻底空了。
21. 23已输出:3, 7, 9, 15, 20五个数升序吐完:3 → 7 → 9 → 15 → 20,和中序遍历分毫不差。栈空了,hasNext() 返回 false,迭代结束。
22. 24弹出顺序 = 中序遍历把弹出顺序连起来看:3 → 7 → 9 → 15 → 20 正是「左→根→右」的中序遍历。栈法不过是把中序遍历拆成一次一步来走而已。
23. 25n 次 next() 总共做 n 次入栈 + n 次出栈,平摊到每次调用就是 O(1)。栈最深只到一条根到叶的路径,所以内存只要 O(h)(h=树高)。
24. 29弹 7 后没 pushLeft(15)如果弹出 7 后忘了对右孩子 15 做 pushLeft,栈就空了,hasNext 直接 false——右子树的 9、15、20 全丢了,序列只剩 3、7。弹出后补右子树的最左链是绝不能漏的一步。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

class BSTIterator:
    def __init__(self, root):
        self.stack = []
        self._push_left(root)        # 先压最左路径
    def _push_left(self, node):
        while node:                  # 一路往左到底
            self.stack.append(node)
            node = node.left
    def next(self):
        node = self.stack.pop()      # 弹栈顶 = 下一个最小
        if node.right:               # 有右孩子就补它的最左链
            self._push_left(node.right)
        return node.val
    def hasNext(self):
        return len(self.stack) > 0

class BSTIterator {
    stack<TreeNode*> st;
    void pushLeft(TreeNode* node) {
        while (node) {                 // 一路往左到底
            st.push(node);
            node = node->left;
        }
    }
public:
    BSTIterator(TreeNode* root) { pushLeft(root); }
    int next() {
        TreeNode* node = st.top(); st.pop();  // 弹栈顶
        if (node->right) pushLeft(node->right);
        return node->val;
    }
    bool hasNext() { return !st.empty(); }
};

class BSTIterator {
    private Deque<TreeNode> stack = new ArrayDeque<>();
    public BSTIterator(TreeNode root) {
        pushLeft(root);                // 先压最左路径
    }
    private void pushLeft(TreeNode node) {
        while (node != null) {         // 一路往左到底
            stack.push(node);
            node = node.left;
        }
    }
    public int next() {
        TreeNode node = stack.pop();   // 弹栈顶
        if (node.right != null) pushLeft(node.right);
        return node.val;
    }
    public boolean hasNext() { return !stack.isEmpty(); }
}

复杂度

面试官可能追问