首页 > 代码库 > 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.
思路：
通过中序遍历将结果保存到一个队列queue中，hasNext()判断queue是否为空，getNext()返回队列头部元素即可
1 public class BSTIterator { 2 private Queue<Integer> queueOfInOrder = new LinkedList<Integer>(); //保存中序遍历得到的队列 3 public BSTIterator(TreeNode root) { 4 InOrder(root); //中序遍历树,得到中序遍历结点队列 5 } 6 7 /** @return whether we have a next smallest number */ 8 public boolean hasNext() { 9 if(queueOfInOrder.isEmpty())10 return false; //队列为空，说明已经最后一个元素11 return true;12 }13 14 /** @return the next smallest number */15 public int next() {16 Integer headOfQueue = queueOfInOrder.poll();17 18 return headOfQueue;19 }20 21 /**22 * 中序遍历树23 */24 private void InOrder(TreeNode root){25 if(null != root){26 InOrder(root.left);27 queueOfInOrder.add(root.val);28 InOrder(root.right);29 }30 }31 }
Binary Search Tree Iterator
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。