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();
 */