"二叉搜索树迭代器的实现与使用"
二叉搜索树(Binary Search Tree, BST)是一种特殊的二叉树结构,其中每个节点的值都大于其左子树中的所有节点值,且小于其右子树中的所有节点值。这使得在BST中进行查找、插入和删除操作具有较高的效率。本题讨论的是如何实现一个按中序遍历顺序迭代BST的迭代器类`BSTIterator`。
在中序遍历BST时,我们通常采用递归或栈的方式遍历节点,依次访问左子树、根节点、右子树。而`BSTIterator`类需要提供两个主要功能:`hasNext()`用于判断是否还有下一个节点,`next()`用于返回下一个节点的值并更新迭代器状态。
在设计`BSTIterator`类时,我们可以利用一个栈来存储待访问的节点。初始化迭代器时,由于BST中最小的元素位于最左侧,我们首先找到最小元素并将所有小于最小元素的节点压入栈中。这样,第一次调用`next()`方法时,就可以直接返回最小元素,之后每次调用`next()`,只需弹出栈顶元素并检查其右子节点,若右子节点不为空则将其及其所有小于它的子节点压入栈中,保证了中序遍历的顺序。
具体代码实现可能如下:
```java
class BSTIterator {
private Stack<TreeNode> stack;
private TreeNode currentNode;
public BSTIterator(TreeNode root) {
stack = new Stack<>();
currentNode = root;
while (currentNode != null) {
stack.push(currentNode);
currentNode = currentNode.left;
}
}
public boolean hasNext() {
return !stack.isEmpty();
}
public int next() {
if (!hasNext()) {
throw new NoSuchElementException();
}
currentNode = stack.pop();
int val = currentNode.val;
currentNode = currentNode.right;
while (currentNode != null) {
stack.push(currentNode);
currentNode = currentNode.left;
}
return val;
}
}
```
在这个实现中,`currentNode`变量用于跟踪当前节点,`stack`用于存储待访问的节点。`hasNext()`方法检查栈是否为空,若非空则表示还有未访问的节点。`next()`方法首先检查是否还有下一个元素,然后弹出栈顶元素(即当前节点),返回其值,并将当前节点更新为其右子节点。如果当前节点的右子节点不为空,我们将其及其所有小于它的子节点压入栈中,以便后续访问。
在给定的测试用例中,输入的数组表示一系列对`BSTIterator`类的操作,如创建迭代器、调用`next()`和`hasNext()`方法。输出的数组表示对应操作的结果。例如,首次调用`next()`返回BST中的最小元素3,之后的调用按照中序遍历顺序返回其他元素。
`BSTIterator`类实现了对二叉搜索树的中序遍历迭代,通过维护一个辅助栈,确保了在`hasNext()`和`next()`方法调用时能按顺序访问BST中的元素。在实际编程中,这样的迭代器设计模式广泛应用于数据结构和算法的实现,尤其是在处理复杂数据结构的遍历需求时。