首页 > 代码库 > LeetCode: Binary Search Tree Iterator 解题报告
LeetCode: 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.
Credits:
Special thanks to @ts for adding this problem and creating all test cases.
Show Tags
Have you met this question in a real interview?
Yes
No
Discuss
SOLUTION 1:
使用inorder traversal把tree转化为arraylist.
递归
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 ArrayList<TreeNode> list;13 int index;14 15 public BSTIterator(TreeNode root) {16 list = new ArrayList<TreeNode>();17 iterator(root, list);18 19 index = 0;20 }21 22 // solution 1: recursion.23 public void dfs (TreeNode root, ArrayList<TreeNode> ret) {24 if (root == null) {25 return;26 }27 28 //Use inorder traversal.29 dfs(root.left, ret);30 ret.add(root);31 dfs(root.right, ret);32 }33 34 35 /** @return whether we have a next smallest number */36 public boolean hasNext() {37 if (index < list.size()) {38 return true;39 }40 41 return false;42 }43 44 /** @return the next smallest number */45 public int next() {46 return list.get(index++).val;47 }48 }49 50 /**51 * Your BSTIterator will be called like this:52 * BSTIterator i = new BSTIterator(root);53 * while (i.hasNext()) v[f()] = i.next();54 */
SOLUTION 2:
the iterator version.
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 ArrayList<TreeNode> list;13 int index;14 15 public BSTIterator(TreeNode root) {16 list = new ArrayList<TreeNode>();17 iterator(root, list);18 19 index = 0;20 }21 22 23 // solution 2: Iterator.24 public void iterator (TreeNode root, ArrayList<TreeNode> ret) {25 if (root == null) {26 return;27 }28 29 Stack<TreeNode> s = new Stack<TreeNode>();30 // bug 1: use push instead of put31 TreeNode cur = root;32 33 while (true) {34 // bug 2: should push the node into the stack.35 while (cur != null) {36 s.push(cur);37 cur = cur.left;38 }39 40 if (s.isEmpty()) {41 break;42 }43 44 // bug 3: should pop a node from the stack.45 // deal with the top node in the satck. 46 cur = s.pop();47 48 // bug 2: should be cur not root.49 ret.add(cur);50 cur = cur.right;51 }52 }53 54 /** @return whether we have a next smallest number */55 public boolean hasNext() {56 if (index < list.size()) {57 return true;58 }59 60 return false;61 }62 63 /** @return the next smallest number */64 public int next() {65 return list.get(index++).val;66 }67 }68 69 /**70 * Your BSTIterator will be called like this:71 * BSTIterator i = new BSTIterator(root);72 * while (i.hasNext()) v[f()] = i.next();73 */
LeetCode: Binary Search Tree Iterator 解题报告
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。