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.

其實這道題的方法就是用迭代來中序遍歷BST，用一個棧來模擬。為什么用迭代，因為迭代才可以這樣一步一步地輸出next元素，遞歸都是一口氣輸出完。

迭代用stack，棧的最大高度就是樹的高度。

我對這道題唯一有疑問的地方在于next()的average時間復雜度要是O(1)，這里average值得推敲，因為不是每次next()時間復雜度都是O(1)的。

因為一個node pop()之后，需要把它右子樹node入棧，不僅如此，還需要沿著右子樹node的左子樹一路push下去，直到這一路全部入棧。這樣做我不確定時間復雜度是O(1), 因為worst case時間復雜度可以到O(N). 比如：

1

/

2

/

3

/

4

1節(jié)點pop()了之后，需要把2、3、4節(jié)點依次入棧，該次復雜度達到了O（N）。但是轉念想想，4、3、2出棧的時候時間復雜度都是O(1)，所以average的情況可以算是O（1）吧，值得推敲。一般不是這么極端的例子，1節(jié)點右子樹節(jié)點2的左節(jié)點這一路應該是常數(shù)個節(jié)點，所以average入棧時間應該是O（1）

 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     Stack<TreeNode> st;13 14     public BSTIterator(TreeNode root) {15         st = new Stack<TreeNode>();16         pushLeft(root);17     }18     19     public void pushLeft(TreeNode root) {20         while (root != null) {21             st.push(root);22             root = root.left;23         }24     }25 26     /** @return whether we have a next smallest number */27     public boolean hasNext() {28         return !st.isEmpty();29     }30 31     /** @return the next smallest number */32     public int next() {33         TreeNode current = st.pop();34         pushLeft(current.right);35         return current.val;36     }37 }38 39 /**40  * Your BSTIterator will be called like this:41  * BSTIterator i = new BSTIterator(root);42  * while (i.hasNext()) v[f()] = i.next();43  */