脚本宝典收集整理的这篇文章主要介绍了[Leetcode - Tree] Binary Search Tree Iterator,脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。
Binary Search Tree Iterator
Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.
Calling next() will return the next smallest number in the BST.
Note: next() and hasNext() should run in average O(1) time and uses O(h) memory, where h is the height of the tree.
1.解题思路
对于二叉搜索树,我们很容易会想到使用栈和队列来解决问题,本题是要求实现一个对二叉搜索树的遍历器,要求每次可以返回最小的节点值,我们使用栈。
1)hasnext(),很容易实现,只要判断栈是否为空;
2)BSTIterator构造函数,我们可以从根节点开始,陆续将左节点压入栈中,这样迭代器构造完后,栈顶元素就是最小的;
3)next(),每次pop出的栈顶元素,该元素肯定不会有左节点,但是我们需要判断其是否有右节点,如果有,我们要将右节点压入栈中,而且还要继续将右节点下面的所有左节点压入栈中,这样才能保证栈顶元素就是最小的。
2.代码
public class BSTIterator {
Stack<TreeNode> s=new Stack<TreeNode>();
public BSTIterator(TreeNode root) {
if(root!=null){
s.push(root);
pushLeft(root);
}
}
/** @return whether we have a next smallest number */
public boolean hasNext() {
return !s.empty();
}
/** @return the next smallest number */
public int next() {
TreeNode node=s.pop();
int value=node.val;
TreeNode rnode=node.right;
if(rnode!=null){
s.push(rnode);
pushLeft(rnode);
}
return value;
}
private void pushLeft(TreeNode root){
TreeNode node=root.left;
while(node!=null){
s.push(node);
node=node.left;
}
}
}
以上是脚本宝典为你收集整理的[Leetcode - Tree] Binary Search Tree Iterator全部内容,希望文章能够帮你解决[Leetcode - Tree] Binary Search Tree Iterator所遇到的问题。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。