Article / 文章
LeetCode 第173题：二叉搜索树迭代器
实现一个二叉搜索树迭代器 BSTIterator 类： - BSTIterator(TreeNode root) 初始化 BSTIterator 类的一个对象。BST 的根节点 root 会作为构造函数的一部分给出。指针应初始化为一个不存在于 BST 中的数字，且该数字小于 BST 中的任何元素。 - boolean hasNext() 如果向指针右侧遍历存
题目描述
实现一个二叉搜索树迭代器 BSTIterator 类：
BSTIterator(TreeNode root)初始化BSTIterator类的一个对象。BST 的根节点root会作为构造函数的一部分给出。指针应初始化为一个不存在于 BST 中的数字，且该数字小于 BST 中的任何元素。boolean hasNext()如果向指针右侧遍历存在数字，则返回true；否则返回false。int next()将指针向右移动，然后返回指针处的数字。
注意，指针初始化为一个不存在于 BST 中的数字，所以对 next() 的首次调用将返回 BST 中的最小元素。
你可以假设 next() 调用总是有效的，也就是说，当调用 next() 时，BST 的中序遍历中至少存在一个下一个数字。
难度
中等
题目链接
示例
示例：
输入
["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]
解释
BSTIterator bSTIterator = new BSTIterator([7, 3, 15, null, null, 9, 20]);
bSTIterator.next(); // 返回 3
bSTIterator.next(); // 返回 7
bSTIterator.hasNext(); // 返回 True
bSTIterator.next(); // 返回 9
bSTIterator.hasNext(); // 返回 True
bSTIterator.next(); // 返回 15
bSTIterator.hasNext(); // 返回 True
bSTIterator.next(); // 返回 20
bSTIterator.hasNext(); // 返回 False提示
- 树中节点的数目在范围
[1, 10^5]内 0 <= Node.val <= 10^6- 最多调用
10^5次hasNext和next操作
进阶
- 你可以设计一个满足下述条件的解决方案吗？
next()和hasNext()操作均摊时间复杂度为 O(1)，并使用 O(h) 内存，其中 h 是树的高度。
解题思路
方法一：提前中序遍历
一种直接的解法是在构造函数中对二叉搜索树进行中序遍历，将结果存储在数组中，然后通过数组索引实现迭代器。 关键点：
- 在构造函数中对BST进行中序遍历，将结果存储在数组中
- 维护一个索引指向当前位置
next()返回当前索引位置的值并将索引加1hasNext()检查当前索引是否小于数组长度
时间复杂度：
- 构造函数: O(n)，其中n是树中节点的数量
next(): O(1)hasNext(): O(1)
空间复杂度：O(n)，需要存储全部节点值
方法二：受控递归（栈）
为了满足进阶要求，我们可以使用栈模拟中序遍历的过程，并在需要时才进行节点访问。 关键点：
- 使用栈模拟中序遍历
- 在构造函数中，沿着最左路径将节点入栈
next()弹出栈顶节点，返回其值，并对其右子树重复步骤2hasNext()检查栈是否为空
时间复杂度：
- 构造函数: O(h)，其中h是树的高度
next(): 均摊O(1)，因为每个节点最多被访问两次hasNext(): O(1)
空间复杂度：O(h)，栈的最大深度为树的高度
代码实现
C# 实现
方法一：提前中序遍历
/**
* Definition for a binary tree node.
* public class TreeNode {
* public int val;
* public TreeNode left;
* public TreeNode right;
* public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
public class BSTIterator {
private List<int> inorderValues;
private int currentIndex;
public BSTIterator(TreeNode root) {
inorderValues = new List<int>();
currentIndex = 0;
InorderTraversal(root);
}
private void InorderTraversal(TreeNode root) {
if (root == null) return;
InorderTraversal(root.left);
inorderValues.Add(root.val);
InorderTraversal(root.right);
}
public int Next() {
return inorderValues[currentIndex++];
}
public bool HasNext() {
return currentIndex < inorderValues.Count;
}
}方法二：受控递归（栈）
public class BSTIterator {
private Stack<TreeNode> stack;
public BSTIterator(TreeNode root) {
stack = new Stack<TreeNode>();
LeftmostInorder(root);
}
private void LeftmostInorder(TreeNode root) {
while (root != null) {
stack.Push(root);
root = root.left;
}
}
public int Next() {
TreeNode node = stack.Pop();
// 如果存在右子树，需要对右子树进行同样的处理
if (node.right != null) {
LeftmostInorder(node.right);
}
return node.val;
}
public bool HasNext() {
return stack.Count > 0;
}
}Python 实现
方法一：提前中序遍历
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class BSTIterator:
def __init__(self, root: Optional[TreeNode]):
self.inorder_values = []
self.current_index = 0
self._inorder_traversal(root)
def _inorder_traversal(self, root):
if not root:
return
self._inorder_traversal(root.left)
self.inorder_values.append(root.val)
self._inorder_traversal(root.right)
def next(self) -> int:
val = self.inorder_values[self.current_index]
self.current_index += 1
return val
def hasNext(self) -> bool:
return self.current_index < len(self.inorder_values)方法二：受控递归（栈）
class BSTIterator:
def __init__(self, root: Optional[TreeNode]):
self.stack = []
self._leftmost_inorder(root)
def _leftmost_inorder(self, root):
while root:
self.stack.append(root)
root = root.left
def next(self) -> int:
node = self.stack.pop()
# 如果存在右子树，需要对右子树进行同样的处理
if node.right:
self._leftmost_inorder(node.right)
return node.val
def hasNext(self) -> bool:
return len(self.stack) > 0C++ 实现
方法一：提前中序遍历
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class BSTIterator {
private:
vector<int> inorderValues;
int currentIndex;
void inorderTraversal(TreeNode* root) {
if (root == nullptr) return;
inorderTraversal(root->left);
inorderValues.push_back(root->val);
inorderTraversal(root->right);
}
public:
BSTIterator(TreeNode* root) {
currentIndex = 0;
inorderTraversal(root);
}
int next() {
return inorderValues[currentIndex++];
}
bool hasNext() {
return currentIndex < inorderValues.size();
}
};方法二：受控递归（栈）
class BSTIterator {
private:
stack<TreeNode*> stk;
void leftmostInorder(TreeNode* root) {
while (root != nullptr) {
stk.push(root);
root = root->left;
}
}
public:
BSTIterator(TreeNode* root) {
leftmostInorder(root);
}
int next() {
TreeNode* node = stk.top();
stk.pop();
// 如果存在右子树，需要对右子树进行同样的处理
if (node->right != nullptr) {
leftmostInorder(node->right);
}
return node->val;
}
bool hasNext() {
return !stk.empty();
}
};性能分析
各语言实现的性能对比（以方法二为例）：
| 实现语言 | 执行用时 | 内存消耗 | 特点 |
|---|---|---|---|
| C# | 152 ms | 48.7 MB | 实现清晰，性能适中 |
| Python | 64 ms | 20.4 MB | 代码最简洁 |
| C++ | 24 ms | 24.1 MB | 性能最优 |
补充说明
代码亮点
- 方法二使用栈模拟中序遍历，符合进阶要求
- 延迟执行下一步操作，实现了均摊O(1)的时间复杂度
- 空间复杂度降低到O(h)，其中h是树的高度
常见错误
- 在方法二中没有正确处理右子树
- 混淆了栈的使用方式，导致遍历顺序错误
- 没有正确理解BST的中序遍历特性（中序遍历得到的是有序序列）