思路：
题目要求的迭代器方法next()返回的是二叉搜索树中下一个最小的元素
对于二叉搜索树来说，它的中序遍历结果是一个升序序列，那么先对二叉搜索树进行先序遍历后，得到的结果我们存在队列中，每次调用next()方法时，从队列的头部弹出一个元素返回，这个元素就是当前二叉搜索树中下一个最小的元素，调用hasNext()时，直接判断队列是否为空即可。
class BSTIterator { private TreeNode root; private Deque<TreeNode> queue = new LinkedList<>(); // 初始化对象时，直接对二叉搜索树进行先序遍历 public BSTIterator(TreeNode root) { this.root = root; this.inorder(root); } // 对二叉搜索树进行先序遍历，将结果存入队列中 private void inorder(TreeNode root) { if (root == null) { return; } inorder(root.left); queue.add(root); inorder(root.right); } /** @return the next smallest number */ public int next() { return queue.removeFirst().val; } /** @return whether we have a next smallest number */ public boolean hasNext() { return !queue.isEmpty(); } } class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } }
