原题
实现一个二叉搜索树迭代器。你将使用二叉搜索树的根节点初始化迭代器。
调用 next() 将返回二叉搜索树中的下一个最小的数。
示例：
BSTIterator iterator = new BSTIterator(root);
iterator.next(); // 返回 3
iterator.next(); // 返回 7
iterator.hasNext(); // 返回 true
iterator.next(); // 返回 9
iterator.hasNext(); // 返回 true
iterator.next(); // 返回 15
iterator.hasNext(); // 返回 true
iterator.next(); // 返回 20
iterator.hasNext(); // 返回 false
提示：
next()和hasNext()操作的时间复杂度是 O(1)，并使用 O(h) 内存，其中 h 是树的高度。- 你可以假设
next()调用总是有效的，也就是说，当调用next()时，BST 中至少存在一个下一个最小的数。
解法
思想
理解二叉搜索树的数据结构，像二叉树的中序遍历那样构造一个list。
代码
class BSTIterator {
List<TreeNode> list;
int cur;
public BSTIterator(TreeNode root) {
list = new ArrayList<>();
cur = -1;
buildList(root);
}
public void buildList(TreeNode root){
if(root == null) return;
buildList(root.left);
list.add(root);
buildList(root.right);
}
/** @return the next smallest number */
public int next() {
cur++;
return list.get(cur).val;
}
/** @return whether we have a next smallest number */
public boolean hasNext() {
if(cur<list.size()-1) return true;
return false;
}
}
原创文章，作者：彭晨涛，如若转载，请注明出处：https://www.codetool.top/article/leetcode173-%e4%ba%8c%e5%8f%89%e6%90%9c%e7%b4%a2%e6%a0%91%e8%bf%ad%e4%bb%a3%e5%99%a8/
