题目描述
思路解析动画文字版
能用,但要先存下全部 n 个值,内存 O(n)。树很大时太浪费——面试官想看的是只花树高 O(h)内存的做法。
中序遍历就是「一直往左走到底,这个最左节点就是当下最小的」。我们把这条往左走的路径压进栈,栈顶永远是下一个该输出的最小值。
弹出栈顶后,它的左边早走完了,接下来该轮到它的右子树里最小的——所以对右孩子再来一次「往左到底」。下面用真树演一遍。
这棵 BST：盯住两样东西:左下这棵树里高亮的节点,和右侧栈的内容。栈顶画在最上面——它就是「下一个要吐出来的数」。
初始化 · 从根出发：初始化做一件事:pushLeft(根)。指针先落在根 7 上,准备沿左边一路压栈。
初始化 · pushLeft(根 7)：把 7 压栈。7 有左孩子 3,所以还没到底,指针移到 3,继续往左。
初始化 · pushLeft 到底：再把 3 压栈。3 没有左孩子,「往左到底」结束。此刻栈顶 3 就是整棵树最小的数——初始化完成。
next() ① · 弹出栈顶 3：调 next():弹出栈顶 3 作为返回值。检查 3 有没有右孩子——没有,所以不用补任何东西。新栈顶变成 7。
输出序列 · 3：3 已经吐出(变灰)。栈里只剩 7,它就是下一个最小。
next() ② · 弹出栈顶 7：再调 next():弹出 7。这次 7 有右孩子 15——7 左边和它自己都处理完了,接下来轮到右子树里最小的,所以对 15 做 pushLeft。
next() ② · 移到右孩子 15：指针移到 7 的右孩子 15。现在对它「往左到底」,把这条新的最左链补进栈。
next() ② · pushLeft(15) 压 15：从右孩子 15 起再「往左到底」:先压 15。15 有左孩子 9,还没到底。
next() ② · pushLeft 到底：再压 9,9 没有左孩子,停。栈变成 [15, 9],栈顶 9 是当前最小。这一次 next() 返回的是刚弹出的 7。
输出序列 · 7：输出序列到了 3, 7。栈里现在是 15(底)、9(顶),下一个该吐 9。
next() ③ · 弹出栈顶 9：next():弹出栈顶 9。9 没有右孩子,不补。新栈顶回到 15。
输出序列 · 9：9 吐出。栈里只剩 15,它是下一个最小。
next() ④ · 弹出栈顶 15：next():弹出 15。15 有右孩子 20,对 20 做 pushLeft。
next() ④ · pushLeft(20) 压 20：从 20 往左:压 20,20 没有左孩子,立刻到底。栈现在只有一个 20。本次 next() 返回的是刚弹出的 15。
输出序列 · 15：输出到 3, 7, 9, 15。只剩栈顶 20 没吐了。
next() ⑤ · 弹出栈顶 20：最后一次 next():弹出 20,它没有右孩子,栈彻底空了。
全部输出完 · hasNext() = false：五个数升序吐完:3 → 7 → 9 → 15 → 20,和中序遍历分毫不差。栈空了,hasNext() 返回 false,迭代结束。
回看 · 这就是中序顺序：把弹出顺序连起来看:3 → 7 → 9 → 15 → 20 正是「左→根→右」的中序遍历。栈法不过是把中序遍历拆成一次一步来走而已。
n 次 next() 总共做 n 次入栈 + n 次出栈,平摊到每次调用就是 O(1)。栈最深只到一条根到叶的路径,所以内存只要 O(h)(h=树高)。
雷区实演 · 漏补右子树：如果弹出 7 后忘了对右孩子 15 做 pushLeft,栈就空了,hasNext 直接 false——右子树的 9、15、20 全丢了,序列只剩 3、7。弹出后补右子树的最左链是绝不能漏的一步。
边界三连：退化成链时 h=n,O(h) 也就成了 O(n)——这是最坏情况,但平衡 BST 下 h=log n。
面试追问：均摊 O(1)、O(h) 内存、双向扩展,是这题面试最常被追的三点。
参考代码
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复杂度
- next() / hasNext()：均摊 O(1)，每个节点一生只入栈一次、出栈一次;n 次调用共 2n 次栈操作,平摊到每次 O(1)
- 空间复杂度：O(h)，栈里最多只放一条「根到叶」路径上的节点,h = 树高(平衡时 log n,最坏 n)
易错点
面试追问把动画讲成自己的话
追问为什么是均摊 O(1) 而不是严格 O(1)?
追问内存为什么是 O(h) 不是 O(n)?
追问怎么扩展成支持 prev()(返回上一个)?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
二叉树右视图
LeetCode 199 · 中等 · 沿着 二叉树套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题