原题
实现一个二叉搜索树迭代器。你将使用二叉搜索树的根节点初始化迭代器。
调用 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/
相关推荐
-
leetcode102-二叉树的层次遍历
原题 给定一个二叉树，返回其按层次遍历的节点值。 （即逐层地，从左到右访问所有节点）。 例如:给定二叉树: [3,9,20,null,null,15,7],  ...
-
leetcode80-删除排序数组中的重复项II
原题 给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素最多出现两次，返回移除后数组的新长度。 不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外...
-
leetcode110-平衡二叉树
原题 给定一个二叉树，判断它是否是高度平衡的二叉树。 本题中，一棵高度平衡二叉树定义为： 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。 示例 1: 给定二叉树 [...
-
leetcode36-有效的数独
原题 判断一个 9x9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。 数字 1-9 在每一行只能出现一次。 数字 1-9 在每一列只能出现一次。 数字 1-...
-
leetcode652-寻找重复的子树
原题 给定一棵二叉树，返回所有重复的子树。对于同一类的重复子树，你只需要返回其中任意一棵的根结点即可。 两棵树重复是指它们具有相同的结构以及相同的结点值。 示例1: 1 / \ 2...
-
leetcode42-接雨水
原题 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。 上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高...
-
leetcode264-丑数II
原题 编写一个程序，找出第 n 个丑数。 丑数就是只包含质因数 2, 3, 5 的正整数。 示例: 输入： n = 10 输出： 12 解释： 1, 2, 3, 4, 5, 6, ...
-
leetcode540-有序数组中的单一元素
原题 给定一个只包含整数的有序数组，每个元素都会出现两次，唯有一个数只会出现一次，找出这个数。 示例1: 输入： [1,1,2,3,3,4,4,8,8] 输出： 2 示例2: 输入...
-
leetcode771-宝石与石头
原题 给定字符串J 代表石头中宝石的类型，和字符串 S代表你拥有的石头。 S 中每个字符代表了一种你拥有的石头的类型，你想知道你拥有的石头中有多少是宝石。 J 中的字母不重复，J ...
-
leetcode119-杨辉三角II
原题 给定一个非负索引 k，其中 k ≤ 33，返回杨辉三角的第 k 行。在杨辉三角中，每个数是它左上方和右上方的数的和。 示例: 输入: 3 输出: [1,3,3,1] 进阶： ...