二叉搜索树迭代器
难度:
标签:
题目描述
实现一个二叉搜索树迭代器类
BSTIterator ，表示一个按中序遍历二叉搜索树（BST）的迭代器：
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, 105]内 0 <= Node.val <= 106- 最多调用
105次hasNext和next操作
进阶：
- 你可以设计一个满足下述条件的解决方案吗？
next()和hasNext()操作均摊时间复杂度为O(1)，并使用O(h)内存。其中h是树的高度。
代码结果
运行时间: 80 ms, 内存: 21.8 MB
/*
* Solution for BSTIterator using Java Stream API
*
* Here, instead of explicitly using a stack, we collect the nodes in sorted order
* using an in-order traversal during initialization and store them in a list. This
* allows us to directly access elements in sorted order, but with O(n) space complexity.
*/
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
class BSTIterator {
private List<Integer> inorderList;
private int currentIndex;
public BSTIterator(TreeNode root) {
inorderList = new ArrayList<>();
inorderTraversal(root);
currentIndex = 0;
}
/** @return the next smallest number */
public int next() {
return inorderList.get(currentIndex++);
}
/** @return whether we have a next smallest number */
public boolean hasNext() {
return currentIndex < inorderList.size();
}
// Helper method to perform in-order traversal and collect nodes
private void inorderTraversal(TreeNode root) {
if (root == null) return;
inorderTraversal(root.left);
inorderList.add(root.val);
inorderTraversal(root.right);
}
}
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}解释
方法:
这个题解使用了迭代的方式实现二叉搜索树的中序遍历。在初始化时，通过 dfsLeft 方法将根节点及其所有左子节点压入栈中。在调用 next 方法时，从栈中弹出一个节点，该节点就是当前中序遍历的最小节点。然后对该节点的右子树调用 dfsLeft，将右子树的所有左子节点压入栈中。hasNext 方法通过判断栈是否为空来确定是否还有下一个元素。
时间复杂度:
平均情况下 O(1)，最坏情况下 O(n)
空间复杂度:
平均情况下 O(h)，最坏情况下 O(n)
代码细节讲解
🦆
在`BSTIterator`类的构造函数中，为什么选择先将所有左子节点压入栈中，而不是其他遍历方式？
▷🦆
对于`dfsLeft`方法中，当遇到没有左子树的节点时，如何处理？
▷🦆
在`next`方法中，为什么在弹出栈顶元素后，需要立即对其右子树调用`dfsLeft`方法？
▷🦆
如果二叉搜索树中包含重复值，这种实现方式是否还能正确运行？
▷相关问题
二叉树的中序遍历
给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。
示例 1：
输入：root = [1,null,2,3] 输出：[1,3,2]
示例 2：
输入：root = [] 输出：[]
示例 3：
输入：root = [1] 输出：[1]
提示：
- 树中节点数目在范围
[0, 100]内 -100 <= Node.val <= 100
进阶: 递归算法很简单，你可以通过迭代算法完成吗？
窥视迭代器
请你在设计一个迭代器，在集成现有迭代器拥有的 hasNext 和 next 操作的基础上，还额外支持 peek 操作。
实现 PeekingIterator 类：
PeekingIterator(Iterator<int> nums)使用指定整数迭代器nums初始化迭代器。int next()返回数组中的下一个元素，并将指针移动到下个元素处。bool hasNext()如果数组中存在下一个元素，返回true；否则，返回false。int peek()返回数组中的下一个元素，但 不 移动指针。
注意：每种语言可能有不同的构造函数和迭代器 Iterator，但均支持 int next() 和 boolean hasNext() 函数。
示例 1：
输入： ["PeekingIterator", "next", "peek", "next", "next", "hasNext"] [[[1, 2, 3]], [], [], [], [], []] 输出： [null, 1, 2, 2, 3, false] 解释： PeekingIterator peekingIterator = new PeekingIterator([1, 2, 3]); // [1,2,3] peekingIterator.next(); // 返回 1 ，指针移动到下一个元素 [1,2,3] peekingIterator.peek(); // 返回 2 ，指针未发生移动 [1,2,3] peekingIterator.next(); // 返回 2 ，指针移动到下一个元素 [1,2,3] peekingIterator.next(); // 返回 3 ，指针移动到下一个元素 [1,2,3] peekingIterator.hasNext(); // 返回 False
提示：
1 <= nums.length <= 10001 <= nums[i] <= 1000- 对
next和peek的调用均有效 next、hasNext和peek最多调用1000次
进阶：你将如何拓展你的设计？使之变得通用化，从而适应所有的类型，而不只是整数型？