# 0173. 二叉搜索树迭代器
###### tags: `Leetcode` `Medium` `迭代器`
Link: https://leetcode-cn.com/problems/binary-search-tree-iterator/

## 思路

## Code
### 方法一

### 方法二

## Result

## 思路in Java
### 方法一

class BSTIterator {
    int idx;
    List<Integer> arr;
    public BSTIterator(TreeNode root) {
        this.idx = 0;
        this.arr = new ArrayList<>();
        inorderTraversal(root, arr);
    }

    public int next() {
        return this.arr.get(idx++);
    }

    public boolean hasNext() {
        return idx <= arr.size() - 1;
    }

    private void inorderTraversal(TreeNode root, List<Integer> arr) {
        if (root == null) return;
        inorderTraversal(root.left, arr);
        arr.add(root.val);
        inorderTraversal(root.right, arr);
    }
}

### 思路二
#### 用栈，如下图所示

class BSTIterator {
    Deque<TreeNode> stack;
    TreeNode cur;
    public BSTIterator(TreeNode root) {
        cur = root;
        stack = new ArrayDeque<>();
    }

    public int next() {
        while (cur != null){
            stack.addLast(cur);
            cur = cur.left;
        }
        // 运行到这里说明 cur = null了
        cur = stack.removeLast();
        int res = cur.val;
        cur = cur.right;
        return res;
    }

    public boolean hasNext() {
        return !stack.isEmpty() || cur != null;
    }
}