题目

实现一个二叉搜索树迭代器。你将使用二叉搜索树的根节点初始化迭代器。
调用 next() 将返回二叉搜索树中的下一个最小的数。

示例

思考

因为是搜索树，左边元素始终比右边元素小，使用中序迭代，把元素从小到大放入队列中。

代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class BSTIterator {
    private Queue<Integer> queue = new LinkedList<Integer>();
    public BSTIterator(TreeNode root) {
        travel(root);
    }
    //中序遍历存储到队列中
    public void travel(TreeNode root) {
        if (root == null) 
            return;
        travel(root.left);
        queue.offer(root.val);
        travel(root.right);
    }

    //取出第一个元素并删除
    public int next() {
        return queue.poll();
    }

    //取出第一个元素看是否还有元素
    public boolean hasNext() {
        return queue.peek() != null;
    }
}