解題思路
使用一個ArrayList保存按中序遍歷順序的節(jié)點，因為二叉搜索樹按中序遍歷的結(jié)果是升序的
再定義一個index = -1，先判斷索引index + 1 < nodes.size()是否合法
合法則next()返回ArrayList對應(yīng)索引index + 1的元素
代碼
class BSTIterator {
ArrayList<Integer> nodes = new ArrayList<>();
int index = -1;
public BSTIterator(TreeNode root) {
dfs(root);
}
public int next() {
return nodes.get(++index);
}
public boolean hasNext() {
return index + 1 < nodes.size();
}
private void dfs(TreeNode root) {
if (root == null) {
return;
}
dfs(root.left);
nodes.add(root.val);
dfs(root.right);
}
}
