解法一：前序遍历递归

在构造函数中进行前序遍历递归，获取完整的二叉搜索树节点序列。

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode(int x) { val = x; }
  8.  * }
  9.  */
  10. class BSTIterator {
  11.     List<Integer> list;
  12.     int index = 0;
  14.     public BSTIterator(TreeNode root) {
  15.         list = new LinkedList<>();
  16.         preOrder(root);
  17.     }
  19.     private void preOrder(TreeNode root) {
  20.         if (root == null) {
  21.             return;
  22.         }
  23.         if (root.left != null) {
  24.             preOrder(root.left);
  25.         }
  26.         list.add(root.val);
  27.         if (root.right != null) {
  28.             preOrder(root.right);
  29.         }
  30.     }
  32.     /**
  33.      * @return the next smallest number
  34.      */
  35.     public int next() {
  36.         return list.get(index++);
  37.     }
  39.     /**
  40.      * @return whether we have a next smallest number
  41.      */
  42.     public boolean hasNext() {
  43.         return index < list.size();
  44.     }
  45. }
  47. /**
  48.  * Your BSTIterator object will be instantiated and called as such:
  49.  * BSTIterator obj = new BSTIterator(root);
  50.  * int param_1 = obj.next();
  51.  * boolean param_2 = obj.hasNext();
  52.  */

解法二：用栈模拟递归

用栈模拟递归的过程，这样可以自己控制遍历的开始和终止。
参考官方题解：https://leetcode-cn.com/problems/binary-search-tree-iterator/solution/er-cha-sou-suo-shu-die-dai-qi-by-leetcode/

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode(int x) { val = x; }
  8.  * }
  9.  */
  10. class BSTIterator {
  11.     Deque<TreeNode> stack;
  13.     public BSTIterator(TreeNode root) {
  14.         stack = new LinkedList<>();
  15.         leftOrder(root);
  16.     }
  18.     private void leftOrder(TreeNode root) {
  19.         if (root == null) {
  20.             return;
  21.         }
  22.         stack.push(root);
  23.         if (root.left != null) {
  24.             leftOrder(root.left);
  25.         }
  26.     }
  28.     /**
  29.      * @return the next smallest number
  30.      */
  31.     public int next() {
  32.         TreeNode nextNode = stack.pop();
  33.         if (nextNode.right != null) {
  34.             leftOrder(nextNode.right);
  35.         }
  36.         return nextNode.val;
  37.     }
  39.     /**
  40.      * @return whether we have a next smallest number
  41.      */
  42.     public boolean hasNext() {
  43.         return !stack.isEmpty();
  44.     }
  45. }
  46. /**
  47.  * Your BSTIterator object will be instantiated and called as such:
  48.  * BSTIterator obj = new BSTIterator(root);
  49.  * int param_1 = obj.next();
  50.  * boolean param_2 = obj.hasNext();
  51.  */