算法题
算法刷题专栏 | 面试必备算法 | 面试高频算法 越难的东西,越要努力坚持，因为它具有很高的价值，算法就是这样✨ 作者简介：硕风和炜，CSDN-Java领域优质创作者，保研|国家奖学金|高中学习JAVA|大学完善JAVA开发技术栈|面试刷题|面经八股文|经验分享|好用的网站工具分享 恭喜你发现一枚宝藏博主,赶快收入囊中吧 人生如棋，我愿为卒，行动虽慢，可谁曾见我后退一步？
算法题
目录
题目链接⛲ 题目描述 求解思路&实现代码&运行结果⚡ dfs + 二叉搜索树復 求解思路復 实现代码復 运行结果
共勉
题目链接
173. 二叉搜索树迭代器
⛲ 题目描述
实现一个二叉搜索树迭代器类BSTIterator ，表示一个按中序遍历二叉搜索树（BST）的迭代器： BSTIterator(TreeNode root) 初始化 BSTIterator 类的一个对象。BST 的根节点 root 会作为构造函数的一部分给出。指针应初始化为一个不存在于 BST 中的数字，且该数字小于 BST 中的任何元素。 boolean hasNext() 如果向指针右侧遍历存在数字，则返回 true ；否则返回 false 。 int next()将指针向右移动，然后返回指针处的数字。 注意，指针初始化为一个不存在于 BST 中的数字，所以对 next() 的首次调用将返回 BST 中的最小元素。
你可以假设 next() 调用总是有效的，也就是说，当调用 next() 时，BST 的中序遍历中至少存在一个下一个数字。
示例：
输入 [“BSTIterator”, “next”, “next”, “hasNext”, “next”, “hasNext”, “next”, “hasNext”, “next”, “hasNext”] [[[7, 3, 15, null, null, 9, 20]], [], [], [], [], [], [], [], [], []] 输出 [null, 3, 7, true, 9, true, 15, true, 20, false]
解释 BSTIterator bSTIterator = new BSTIterator([7, 3, 15, null, null, 9, 20]); bSTIterator.next(); // 返回 3 bSTIterator.next(); // 返回 7 bSTIterator.hasNext(); // 返回 True bSTIterator.next(); // 返回 9 bSTIterator.hasNext(); // 返回 True bSTIterator.next(); // 返回 15 bSTIterator.hasNext(); // 返回 True bSTIterator.next(); // 返回 20 bSTIterator.hasNext(); // 返回 False
提示：
树中节点的数目在范围 [1, 105] 内 0 <= Node.val <= 106 最多调用 105 次 hasNext 和 next 操作
求解思路&实现代码&运行结果
⚡ dfs + 二叉搜索树
復 求解思路
通过dfs对二叉搜索树做中序遍历，获取的结果保存在集合中。最后，通过获得到的集合来实现next()和hasnext()函数。next()函数：每次调用next()函数，通过集合来获取位置的元素，每次调用通过维护一个idx来实现。hasnext()函数：此时如果向指针右侧遍历存在数字，返回true，否则，返回false。通过 idx < arr.size() 来实现。有了基本的思路，接下来我们就来通过代码来实现一下。
復 实现代码
class BSTIterator {
private int idx = 0;
private List
public BSTIterator(TreeNode root) {
dfs(root);
}
public int next() {
return arr.get(idx++);
}
public boolean hasNext() {
return idx < arr.size();
}
private void dfs(TreeNode root) {
if (root == null) {
return;
}
dfs(root.left);
arr.add(root.val);
dfs(root.right);
}
}
復 运行结果
共勉
最后，我想和大家分享一句一直激励我的座右铭，希望可以与大家共勉！
相关文章
您阅读本篇文章共花了：
发表评论