Binary Search Tree Iterator

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.

思路：

通过中序遍历将结果保存到一个队列queue中，hasNext()判断queue是否为空，getNext()返回队列头部元素即可

public class BSTIterator {
    private Queue<Integer> queueOfInOrder = new LinkedList<Integer>();            //保存中序遍历得到的队列
    public BSTIterator(TreeNode root) {
        InOrder(root);                                                            //中序遍历树,得到中序遍历结点队列
    }

    /** @return whether we have a next smallest number */
    public boolean hasNext() {
        if(queueOfInOrder.isEmpty())
            return false;                                                        //队列为空，说明已经最后一个元素
        return true;
    }

    /** @return the next smallest number */
    public int next() {
        Integer headOfQueue = queueOfInOrder.poll();
        
        return headOfQueue;
    }
    
    /**
     * 中序遍历树
     */
    private void InOrder(TreeNode root){
        if(null != root){
            InOrder(root.left);
            queueOfInOrder.add(root.val);
            InOrder(root.right);
        }
    }
}