当前位置： 面试刷题>> 二叉搜索树迭代器(经典算法150题)
### 题目描述
设计并实现一个二叉搜索树迭代器类，该类需要包含以下功能：
- `BSTIterator(TreeNode root)`：构造函数，接收一个二叉搜索树的根节点 `root` 作为输入，并初始化迭代器。
- `next()`：返回二叉搜索树中的下一个最小元素（即中序遍历的下一个节点值）。
- `hasNext()`：检查迭代器中是否还有元素。如果有，则返回 `true`；否则返回 `false`。
注意：
- 你只能使用给定的 `TreeNode` 类型的节点。
- 你可以假设 `next()` 和 `hasNext()` 的调用总是有效的，即调用它们时，树中至少存在一个元素。
### 示例代码
以下是使用 PHP、Python 和 JavaScript 编写的示例代码：
#### PHP 示例
```php
val = $val;
$this->left = $left;
$this->right = $right;
}
}
class BSTIterator {
private $stack;
function __construct($root) {
$this->stack = new SplStack();
$this->pushLeft($root);
}
private function pushLeft($node) {
while ($node !== null) {
$this->stack->push($node);
$node = $node->left;
}
}
function next() {
$node = $this->stack->pop();
$this->pushLeft($node->right);
return $node->val;
}
function hasNext() {
return !$this->stack->isEmpty();
}
}
// 使用示例
$root = new TreeNode(7);
$root->left = new TreeNode(3);
$root->right = new TreeNode(15);
$root->right->left = new TreeNode(9);
$root->right->right = new TreeNode(20);
$iterator = new BSTIterator($root);
while ($iterator->hasNext()) {
echo $iterator->next() . " ";
}
// 输出应为：3 7 9 15 20
?>
```
#### Python 示例
```python
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):
self.stack = []
self.pushLeft(root)
def pushLeft(self, node):
while node:
self.stack.append(node)
node = node.left
def next(self):
node = self.stack.pop()
self.pushLeft(node.right)
return node.val
def hasNext(self):
return len(self.stack) > 0
# 使用示例
root = TreeNode(7)
root.left = TreeNode(3)
root.right = TreeNode(15)
root.right.left = TreeNode(9)
root.right.right = TreeNode(20)
iterator = BSTIterator(root)
while iterator.hasNext():
print(iterator.next(), end=" ")
# 输出应为：3 7 9 15 20
```
#### JavaScript 示例
```javascript
class TreeNode {
constructor(val = 0, left = null, right = null) {
this.val = val;
this.left = left;
this.right = right;
}
}
class BSTIterator {
constructor(root) {
this.stack = [];
this.pushLeft(root);
}
pushLeft(node) {
while (node) {
this.stack.push(node);
node = node.left;
}
}
next() {
const node = this.stack.pop();
this.pushLeft(node.right);
return node.val;
}
hasNext() {
return this.stack.length > 0;
}
}
// 使用示例
const root = new TreeNode(7);
root.left = new TreeNode(3);
root.right = new TreeNode(15);
root.right.left = new TreeNode(9);
root.right.right = new TreeNode(20);
const iterator = new BSTIterator(root);
while (iterator.hasNext()) {
console.log(iterator.next());
}
// 输出应为：3 7 9 15 20
```
以上代码展示了如何在 PHP、Python 和 JavaScript 中实现一个二叉搜索树迭代器，按照中序遍历的顺序返回节点值。这些实现都利用了栈来辅助完成中序遍历的非递归实现。