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();
*/
我這個(gè)做法為什么慢，因?yàn)锳rrayList的remove是O(N)的，稍作改進(jìn)黎泣，只用get就大幅度提高了performance到beat 76.09 %. 說明Data structure的基礎(chǔ)確實(shí)很重要，熟悉這些基礎(chǔ)知識(shí)在實(shí)際運(yùn)用時(shí)才能很快作出抉擇缤谎。然而題目要求
Note: next() and hasNext() should run in average O(1) time and uses O(h) memory, where h is the height of the tree.這個(gè)方法空間復(fù)雜度是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();
*/
其實(shí)這個(gè)用ArrayList這個(gè)方法跟stack的方法就基本上沒有差別了,本質(zhì)上還是考的in order traversal的iterative. 雖然stack的方法滿足了Space O(h), 但是performance出來的結(jié)果并不好，只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();
*/
