Description:

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.

解法：

首先来复习一下二叉搜索树的概念。二叉查找树（Binary Search Tree），（又：二叉搜索树，二叉排序树）它或者是一棵空树，或者是具有下列性质的二叉树：若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；它的左、右子树也分别为二叉排序树。这样一来，相当于给一棵搜索树，按从小到大的顺序输出排序结果。由搜索树的性质可知，采用二叉树的中序遍历可以得到该序列。借助栈的帮助可以完成遍历。具体代码如下：

public class BSTIterator {
    private Stack<TreeNode> s = new Stack<TreeNode>();

    public BSTIterator(TreeNode root) {
        TreeNode cur = root;
        while (cur != null) {
            s.push(cur);
            cur = cur.left;
        }
    }
    
    /**
     * @return whether we have a next smallest number
     */
    public boolean hasNext() {
        if (!s.empty()) {
            return true;
        }
        return false;
    }
    
    /**
     * @return the next smallest number
     */
    public int next() {
        TreeNode cur = s.pop();
        int result = cur.val;
        cur = cur.right;
        while (cur != null) {
            s.push(cur);
            cur = cur.left;
        }
        return result;
    }
}