Medium
自己写出来的，但是Runtime太慢了,击败1.31%...
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class BSTIterator {
//BST inOrder
List<Integer> inOrder;
public BSTIterator(TreeNode root) {
inOrder = new ArrayList<>();
inOrderTraverse(root);
}
private void inOrderTraverse(TreeNode root){
if (root == null){
return;
}
inOrderTraverse(root.left);
inOrder.add(root.val);
inOrderTraverse(root.right);
}
/** @return whether we have a next smallest number */
public boolean hasNext() {
return inOrder.size() != 0;
}
/** @return the next smallest number */
public int next() {
if (hasNext()){
return inOrder.remove(0);
}
return -1;
}
}
/**
* Your BSTIterator will be called like this:
* BSTIterator i = new BSTIterator(root);
* while (i.hasNext()) v[f()] = i.next();
*/
我这个做法为什么慢，因为ArrayList的remove是O(N)的，稍作改进，只用get就大幅度提高了performance到beat 76.09 %. 说明Data structure的基础确实很重要，熟悉这些基础知识在实际运用时才能很快作出抉择。然而题目要求
Note: next() and hasNext() should run in average O(1) time and uses O(h) memory, where h is the height of the tree.这个方法空间复杂度是O(N)，超过要求的O(h)了.
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class BSTIterator {
//BST inOrder
List<Integer> inOrder;
int index = 0;
public BSTIterator(TreeNode root) {
inOrder = new ArrayList<>();
inOrderTraverse(root);
}
private void inOrderTraverse(TreeNode root){
if (root == null){
return;
}
inOrderTraverse(root.left);
inOrder.add(root.val);
inOrderTraverse(root.right);
}
/** @return whether we have a next smallest number */
public boolean hasNext() {
return index != inOrder.size();
}
/** @return the next smallest number */
public int next() {
if (hasNext()){
return inOrder.get(index++);
}
return -1;
}
}
/**
* Your BSTIterator will be called like this:
* BSTIterator i = new BSTIterator(root);
* while (i.hasNext()) v[f()] = i.next();
*/
用O(h) space + ArrayList的
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class BSTIterator {
//BST inOrder
List<TreeNode> mins;
public BSTIterator(TreeNode root) {
mins = new ArrayList<>();
while (root != null){
mins.add(root);
root = root.left;
}
}
/** @return whether we have a next smallest number*/
public boolean hasNext() {
return mins.size() > 0;
}
/** @return the next smallest number */
public int next() {
TreeNode smallest = mins.remove(mins.size() - 1);
TreeNode right = smallest.right;
while (right != null){
mins.add(right);
right = right.left;
}
return smallest.val;
}
}
/**
* Your BSTIterator will be called like this:
* BSTIterator i = new BSTIterator(root);
* while (i.hasNext()) v[f()] = i.next();
*/
其实这个用ArrayList这个方法跟stack的方法就基本上没有差别了,本质上还是考的in order traversal的iterative. 虽然stack的方法满足了Space O(h), 但是performance出来的结果并不好，只beat了20%左右
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class BSTIterator {
//BST inOrder
Stack<TreeNode> stack;
public BSTIterator(TreeNode root) {
stack = new Stack<>();
while (root != null){
stack.push(root);
root = root.left;
}
}
/** @return whether we have a next smallest number*/
public boolean hasNext() {
return !stack.isEmpty();
}
/** @return the next smallest number */
public int next() {
TreeNode smallest = stack.pop();
TreeNode right = smallest.right;
while (right != null){
stack.push(right);
right = right.left;
}
return smallest.val;
}
}
/**
* Your BSTIterator will be called like this:
* BSTIterator i = new BSTIterator(root);
* while (i.hasNext()) v[f()] = i.next();
*/
