题目:
难度:Middle
相关话题:栈
、树
、设计
实现一个二叉搜索树迭代器。你将使用二叉搜索树的根节点初始化迭代器。
调用 next()
将返回二叉搜索树中的下一个最小的数。
示例:
BSTIterator iterator = new BSTIterator(root);
iterator.next(); // 返回 3
iterator.next(); // 返回 7
iterator.hasNext(); // 返回 true
iterator.next(); // 返回 9
iterator.hasNext(); // 返回 true
iterator.next(); // 返回 15
iterator.hasNext(); // 返回 true
iterator.next(); // 返回 20
iterator.hasNext(); // 返回 false
提示:
/**
* @来源: Javascript中文网 - 前端进阶资源教程 https://www.javascriptc.com/
* @介绍:一个致力于帮助开发者用代码改变世界为使命的平台,每天都可以在这里找到技术世界的头条内容
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
*/
var BSTIterator = function(root) {
let node=root
let stack=[]
while(node){
stack.push(node)
node=node.left
}
this.stack=stack
};
/**
* @return the next smallest number
* @return {number}
*/
BSTIterator.prototype.next = function() {
let res=this.stack.pop()
let node=res.right
while(node){
this.stack.push(node)
node=node.left
}
return res.val
};
/**
* @return whether we have a next smallest number
* @return {boolean}
*/
BSTIterator.prototype.hasNext = function() {
return this.stack.length>0
};
/**
* Your BSTIterator object will be instantiated and called as such:
* var obj = Object.create(BSTIterator).createNew(root)
* var param_1 = obj.next()
* var param_2 = obj.hasNext()
*/