Leetcode No.173 二叉搜索树迭代器(DFS)
一、题目描述
实现一个二叉搜索树迭代器类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 操作
进阶: 你可以设计一个满足下述条件的解决方案吗?next() 和 hasNext() 操作均摊时间复杂度为 O(1) ,并使用 O(h) 内存。其中 h 是树的高度。
二、解题思路
根据二叉搜索树的性质,不难发现,原问题等价于对二叉搜索树进行中序遍历。因此,我们可以采取与「94. 二叉树的中序遍历」类似的方法来解决这一问题。
下面基于「94. 二叉树的中序遍历的官方题解」,给出本题的解法。读者将不难发现两篇题解的代码存在诸多相似之处。
扁平化 我们可以直接对二叉搜索树做一次完全的递归遍历,获取中序遍历的全部结果并保存在队列中。随后,我们利用得到的队列本身来实现迭代器。
三、代码
import java.util.ArrayDeque;
import java.util.Queue;
class BSTIterator {
Queue<Integer> queue=new ArrayDeque();
public BSTIterator(TreeNode root) {
midTravel(root);
System.out.println();
}
public int next() {
int rs=queue.peek();
queue.poll();
return rs;
}
public boolean hasNext() {
return !queue.isEmpty();
}
public void midTravel(TreeNode root){
if(root==null){
return;
}
if(root.left!=null){
midTravel(root.left);
}
queue.add(root.val);
if(root.right!=null){
midTravel(root.right);
}
}
public static void main(String[] args) {
TreeNode root=new TreeNode(7);
TreeNode node3=new TreeNode(3);
node3.left=null;
node3.right=null;
root.left=node3;
TreeNode node9=new TreeNode(9);
node9.left=null;
node9.right=null;
TreeNode node20=new TreeNode(20);
node20.left=null;
node20.right=null;
TreeNode node15=new TreeNode(15);
node15.left=node9;
node15.right=node20;
root.right=node15;
BSTIterator bst=new BSTIterator(root);
System.out.println();
}
}
四、复杂度分析
时间复杂度:初始化需要 O(n) 的时间,其中 n为树中节点的数量。随后每次调用只需要 O(1) 的时间。
空间复杂度:O(n),因为需要保存中序遍历的全部结果。
相关文章
- 金融服务领域的大数据:即时分析
- 影响大数据、机器学习和人工智能未来发展的8个因素
- 从0开始构建一个属于你自己的PHP框架
- 如何将Hadoop集成到工作流程中?这6个优秀实践必看
- SEO公司使用大数据优化其模型的5种方法
- 关于Web Workers你需要了解的七件事
- 深入理解HTTPS原理、过程与实践
- 增强分析:数据和分析的未来
- PHP协程实现过程详解
- AI专家:大数据知识图谱——实战经验总结
- 关于PHP的错误机制总结
- 利用数据分析量化协同过滤算法的两大常见难题
- 怎么做大数据工作流调度系统?大厂架构师一语点破!
- 2019大数据处理必备的十大工具,从Linux到架构师必修
- OpenCV中的KMeans算法介绍与应用
- 教大家如果搭建一套phpstorm+wamp+xdebug调试PHP的环境
- CentOS下三种PHP拓展安装方法
- Go语言HTTP Server源码分析
- Go语言HTTP Server源码分析
- 2017年4月编程语言排行榜:Hack首次进入前五十