---
# System prepended metadata

title: 0173. 二叉搜索树迭代器
tags: [Leetcode, 迭代器, Medium]

---

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

##  思路

##  Code
###  方法一
```c=

```
###  方法二

## Result




## 思路in Java
### 方法一
```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);
    }
}
```

### 思路二
#### 用栈，如下图所示
![](https://pic.leetcode-cn.com/1616898885-tLjlOD-173.001.jpeg)
```java=
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;
    }
}

```

