173. 二叉搜索树迭代器
题目描述
实现类 BSTIterator，它按中序遍历的顺序逐个取出一棵二叉搜索树中的值。可以把它想成一个在中序序列上移动的指针。
- BSTIterator(TreeNode root)：用根节点 root 创建迭代器。指针最初停在一个比树中所有值都小、且不在树中的位置，因此第一次调用 next() 会得到最小值。
- boolean hasNext()：指针右边还有值时返回 true，否则返回 false。
- int next()：把指针右移一位，返回所指的值。
调用 next() 时一定还有下一个值可取。树以层序数组给出，例如 [7,3,15,null,null,9,20]，null 表示空位。
示例 1
输入：操作 = ["BSTIterator","next","next","hasNext","next","hasNext","next","hasNext","next","hasNext"] 参数 = [[[7,3,15,null,null,9,20]],[],[],[],[],[],[],[],[],[]] 输出：[null,3,7,true,9,true,15,true,20,false]
解释：中序序列是 3、7、9、15、20，next() 依次取出这些值；取完 20 后 hasNext() 返回 false。
数据范围
- 树中节点数在
[1, 10^5]范围内。 0 <= Node.val <= 10^6hasNext和next合计最多调用10^5次。
进阶：能否让 next() 和 hasNext() 的均摊时间为 O(1)，并且只用 O(h) 内存？h 是树高。
解题思路：受控递归（栈模拟中序遍历）
把递归中序遍历拆开，用一个显式栈保存“还没访问的祖先”。构造时把根的整条左链压栈，此时栈顶就是最小值。next 弹出栈顶 node 作为答案；比 node 大的下一个数在它的右子树最左端，所以对 node.right 再压一次左链。hasNext 只需判断栈是否为空。
为什么正确
栈中节点从底到顶严格递减，栈顶是下一个要返回的节点；所有未访问的节点要么在栈里，要么在栈中某个节点的右子树里。
复杂度分析
next 均摊 O(1)（每个节点只入栈、出栈各一次），hasNext O(1)；空间 O(h)。
易错点
弹出节点后只压入 node.right 本身是错的，必须把右子树的整条左链都压入，否则下一个返回的不是最小值。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class BSTIterator:
def __init__(self, root: Optional[TreeNode]):
self.stack = []
self.push_left(root)
def push_left(self, node):
while node:
self.stack.append(node)
node = node.left
def next(self) -> int:
node = self.stack.pop()
self.push_left(node.right)
return node.val
def hasNext(self) -> bool:
return len(self.stack) > 0class BSTIterator {
private final 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();
pushLeft(node.right);
return node.val;
}
public boolean hasNext() {
return !stack.isEmpty();
}
}class BSTIterator {
vector<TreeNode*> st;
public:
BSTIterator(TreeNode* root) {
pushLeft(root);
}
void pushLeft(TreeNode* node) {
while (node) {
st.push_back(node);
node = node->left;
}
}
int next() {
TreeNode* node = st.back();
st.pop_back();
pushLeft(node->right);
return node->val;
}
bool hasNext() {
return !st.empty();
}
};type BSTIterator struct {
stack []*TreeNode
}
func Constructor(root *TreeNode) BSTIterator {
it := BSTIterator{}
it.pushLeft(root)
return it
}
func (this *BSTIterator) pushLeft(node *TreeNode) {
for node != nil {
this.stack = append(this.stack, node)
node = node.Left
}
}
func (this *BSTIterator) Next() int {
node := this.stack[len(this.stack)-1]
this.stack = this.stack[:len(this.stack)-1]
this.pushLeft(node.Right)
return node.Val
}
func (this *BSTIterator) HasNext() bool {
return len(this.stack) > 0
}var BSTIterator = function(root) {
this.stack = [];
this.pushLeft(root);
};
BSTIterator.prototype.pushLeft = function(node) {
while (node) {
this.stack.push(node);
node = node.left;
}
};
BSTIterator.prototype.next = function() {
const node = this.stack.pop();
this.pushLeft(node.right);
return node.val;
};
BSTIterator.prototype.hasNext = function() {
return this.stack.length > 0;
};class BSTIterator {
private stack: TreeNode[] = [];
constructor(root: TreeNode | null) {
this.pushLeft(root);
}
private pushLeft(node: TreeNode | null): void {
while (node) {
this.stack.push(node);
node = node.left;
}
}
next(): number {
const node = this.stack.pop()!;
this.pushLeft(node.right);
return node.val;
}
hasNext(): boolean {
return this.stack.length > 0;
}
}其他解法
展开数组一次性完成全部遍历，占 O(n) 空间；栈解法按需推进遍历，只保存一条左链，空间 O(h)。
解法 2：中序遍历展开成数组 时间 初始化 O(n)，操作 O(1)，空间 O(n)
构造时对整棵树做一次递归中序遍历，把结点值按升序存进数组，并记录一个下标 idx。next() 返回数组[idx] 并让 idx 加一，hasNext() 判断 idx 是否小于数组长度。
实现最简单，每次操作严格 O(1)。要保存整棵树的 n 个值，不满足进阶要求的 O(h) 空间。
class BSTIterator:
def __init__(self, root):
self.vals = []
self.idx = 0
self.inorder(root)
def inorder(self, node):
if node is None:
return
self.inorder(node.left)
self.vals.append(node.val)
self.inorder(node.right)
def next(self) -> int:
self.idx += 1
return self.vals[self.idx - 1]
def hasNext(self) -> bool:
return self.idx < len(self.vals)class BSTIterator {
private final List<Integer> vals = new ArrayList<>();
private int idx = 0;
public BSTIterator(TreeNode root) {
inorder(root);
}
private void inorder(TreeNode node) {
if (node == null) return;
inorder(node.left);
vals.add(node.val);
inorder(node.right);
}
public int next() {
return vals.get(idx++);
}
public boolean hasNext() {
return idx < vals.size();
}
}class BSTIterator {
vector<int> vals;
int idx = 0;
void inorder(TreeNode* node) {
if (!node) return;
inorder(node->left);
vals.push_back(node->val);
inorder(node->right);
}
public:
BSTIterator(TreeNode* root) {
inorder(root);
}
int next() {
return vals[idx++];
}
bool hasNext() {
return idx < (int)vals.size();
}
};type BSTIterator struct {
vals []int
idx int
}
func Constructor(root *TreeNode) BSTIterator {
it := BSTIterator{}
var inorder func(node *TreeNode)
inorder = func(node *TreeNode) {
if node == nil {
return
}
inorder(node.Left)
it.vals = append(it.vals, node.Val)
inorder(node.Right)
}
inorder(root)
return it
}
func (this *BSTIterator) Next() int {
this.idx++
return this.vals[this.idx-1]
}
func (this *BSTIterator) HasNext() bool {
return this.idx < len(this.vals)
}var BSTIterator = function(root) {
this.vals = [];
this.idx = 0;
const inorder = (node) => {
if (!node) return;
inorder(node.left);
this.vals.push(node.val);
inorder(node.right);
};
inorder(root);
};
BSTIterator.prototype.next = function() {
return this.vals[this.idx++];
};
BSTIterator.prototype.hasNext = function() {
return this.idx < this.vals.length;
};class BSTIterator {
private vals: number[] = [];
private idx = 0;
constructor(root: TreeNode | null) {
this.inorder(root);
}
private inorder(node: TreeNode | null): void {
if (!node) return;
this.inorder(node.left);
this.vals.push(node.val);
this.inorder(node.right);
}
next(): number {
return this.vals[this.idx++];
}
hasNext(): boolean {
return this.idx < this.vals.length;
}
}