| comments | difficulty | edit_url | tags | ||||||
|---|---|---|---|---|---|---|---|---|---|
true |
中等 |
|
实现二叉搜索树（BST）的中序遍历迭代器 BSTIterator 类：
BSTIterator(TreeNode root)初始化BSTIterator类的实例。二叉搜索树的根节点root作为构造函数的参数传入。内部指针使用一个不存在于树中且小于树中任意值的数值来初始化。boolean hasNext()如果当前指针在中序遍历序列中，存在右侧数值，返回true，否则返回false。int next()将指针在中序遍历序列中向右移动，然后返回移动后指针所指数值。boolean hasPrev()如果当前指针在中序遍历序列中，存在左侧数值，返回true，否则返回false。int prev()将指针在中序遍历序列中向左移动，然后返回移动后指针所指数值。
注意，虽然我们使用树中不存在的最小值来初始化内部指针，第一次调用 next() 需要返回二叉搜索树中最小的元素。
你可以假设 next() 和 prev() 的调用总是有效的。即，当 next()/prev() 被调用的时候，在中序遍历序列中一定存在下一个/上一个元素。
进阶：你可以不提前遍历树中的值来解决问题吗？
示例 1:
输入 ["BSTIterator", "next", "next", "prev", "next", "hasNext", "next", "next", "next", "hasNext", "hasPrev", "prev", "prev"] [[[7, 3, 15, null, null, 9, 20]], [null], [null], [null], [null], [null], [null], [null], [null], [null], [null], [null], [null]] 输出 [null, 3, 7, 3, 7, true, 9, 15, 20, false, true, 15, 9] 解释 // 划线的元素表示指针当前的位置。 BSTIterator bSTIterator = new BSTIterator([7, 3, 15, null, null, 9, 20]); // 当前状态为 <u> </u> [3, 7, 9, 15, 20] bSTIterator.next(); // 状态变为 [<u>3</u>, 7, 9, 15, 20], 返回 3 bSTIterator.next(); // 状态变为 [3, <u>7</u>, 9, 15, 20], 返回 7 bSTIterator.prev(); // 状态变为 [<u>3</u>, 7, 9, 15, 20], 返回 3 bSTIterator.next(); // 状态变为 [3, <u>7</u>, 9, 15, 20], 返回 7 bSTIterator.hasNext(); // 返回 true bSTIterator.next(); // 状态变为 [3, 7, <u>9</u>, 15, 20], 返回 9 bSTIterator.next(); // 状态变为 [3, 7, 9, <u>15</u>, 20], 返回 15 bSTIterator.next(); // 状态变为 [3, 7, 9, 15, <u>20</u>], 返回 20 bSTIterator.hasNext(); // 返回 false bSTIterator.hasPrev(); // 返回 true bSTIterator.prev(); // 状态变为 [3, 7, 9, <u>15</u>, 20], 返回 15 bSTIterator.prev(); // 状态变为 [3, 7, <u>9</u>, 15, 20], 返回 9
提示:
- 树中节点个数的范围是
[1, 105]。 0 <= Node.val <= 106- 最多调用 105 次
hasNext、next、hasPrev和prev。
我们可以使用中序遍历将二叉搜索树的所有节点的值存储到数组
时间复杂度方面，初始化迭代器需要
# 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.nums = []
def dfs(root):
if root is None:
return
dfs(root.left)
self.nums.append(root.val)
dfs(root.right)
dfs(root)
self.i = -1
def hasNext(self) -> bool:
return self.i < len(self.nums) - 1
def next(self) -> int:
self.i += 1
return self.nums[self.i]
def hasPrev(self) -> bool:
return self.i > 0
def prev(self) -> int:
self.i -= 1
return self.nums[self.i]
# Your BSTIterator object will be instantiated and called as such:
# obj = BSTIterator(root)
# param_1 = obj.hasNext()
# param_2 = obj.next()
# param_3 = obj.hasPrev()
# param_4 = obj.prev()/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class BSTIterator {
private List<Integer> nums = new ArrayList<>();
private int i = -1;
public BSTIterator(TreeNode root) {
dfs(root);
}
public boolean hasNext() {
return i < nums.size() - 1;
}
public int next() {
return nums.get(++i);
}
public boolean hasPrev() {
return i > 0;
}
public int prev() {
return nums.get(--i);
}
private void dfs(TreeNode root) {
if (root == null) {
return;
}
dfs(root.left);
nums.add(root.val);
dfs(root.right);
}
}
/**
* Your BSTIterator object will be instantiated and called as such:
* BSTIterator obj = new BSTIterator(root);
* boolean param_1 = obj.hasNext();
* int param_2 = obj.next();
* boolean param_3 = obj.hasPrev();
* int param_4 = obj.prev();
*//**
* 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 {
public:
BSTIterator(TreeNode* root) {
dfs(root);
n = nums.size();
}
bool hasNext() {
return i < n - 1;
}
int next() {
return nums[++i];
}
bool hasPrev() {
return i > 0;
}
int prev() {
return nums[--i];
}
private:
vector<int> nums;
int i = -1;
int n;
void dfs(TreeNode* root) {
if (!root) {
return;
}
dfs(root->left);
nums.push_back(root->val);
dfs(root->right);
}
};
/**
* Your BSTIterator object will be instantiated and called as such:
* BSTIterator* obj = new BSTIterator(root);
* bool param_1 = obj->hasNext();
* int param_2 = obj->next();
* bool param_3 = obj->hasPrev();
* int param_4 = obj->prev();
*//**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
type BSTIterator struct {
nums []int
i, n int
}
func Constructor(root *TreeNode) BSTIterator {
nums := []int{}
var dfs func(*TreeNode)
dfs = func(root *TreeNode) {
if root == nil {
return
}
dfs(root.Left)
nums = append(nums, root.Val)
dfs(root.Right)
}
dfs(root)
return BSTIterator{nums, -1, len(nums)}
}
func (this *BSTIterator) HasNext() bool {
return this.i < this.n-1
}
func (this *BSTIterator) Next() int {
this.i++
return this.nums[this.i]
}
func (this *BSTIterator) HasPrev() bool {
return this.i > 0
}
func (this *BSTIterator) Prev() int {
this.i--
return this.nums[this.i]
}
/**
* Your BSTIterator object will be instantiated and called as such:
* obj := Constructor(root);
* param_1 := obj.HasNext();
* param_2 := obj.Next();
* param_3 := obj.HasPrev();
* param_4 := obj.Prev();
*//**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
class BSTIterator {
private nums: number[];
private n: number;
private i: number;
constructor(root: TreeNode | null) {
this.nums = [];
const dfs = (root: TreeNode | null) => {
if (!root) {
return;
}
dfs(root.left);
this.nums.push(root.val);
dfs(root.right);
};
dfs(root);
this.n = this.nums.length;
this.i = -1;
}
hasNext(): boolean {
return this.i < this.n - 1;
}
next(): number {
return this.nums[++this.i];
}
hasPrev(): boolean {
return this.i > 0;
}
prev(): number {
return this.nums[--this.i];
}
}
/**
* Your BSTIterator object will be instantiated and called as such:
* var obj = new BSTIterator(root)
* var param_1 = obj.hasNext()
* var param_2 = obj.next()
* var param_3 = obj.hasPrev()
* var param_4 = obj.prev()
*/