首页 > 代码库 > LeetCode Binary Search Tree Iterator
LeetCode 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.
Credits:
Special thanks to @ts for adding this problem and creating all test cases.
在构造器中，中序遍历所有节点，加入队列中，然后操作队列就行。
1 /** 2 * Definition for binary tree 3 * public class TreeNode { 4 * int val; 5 * TreeNode left; 6 * TreeNode right; 7 * TreeNode(int x) { val = x; } 8 * } 9 */10 11 public class BSTIterator {12 13 Queue<Integer> queue; 14 public BSTIterator(TreeNode root) {15 queue = new LinkedList<Integer>();16 midOrder(root);17 18 }19 20 private void midOrder(TreeNode root) {21 if (root == null) {22 return;23 }24 midOrder(root.left);25 queue.add(root.val);26 midOrder(root.right);27 }28 29 30 /** @return whether we have a next smallest number */31 public boolean hasNext() {32 return !queue.isEmpty();33 }34 35 /** @return the next smallest number */36 public int next() {37 return queue.poll();38 }39 }40 41 /**42 * Your BSTIterator will be called like this:43 * BSTIterator i = new BSTIterator(root);44 * while (i.hasNext()) v[f()] = i.next();45 */
LeetCode Binary Search Tree Iterator
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。