【Leetcode刷题篇】leetcode173 二叉搜索树迭代器
发布日期:2021-06-29 15:33:27
浏览次数:2
分类:技术文章
本文共 1589 字,大约阅读时间需要 5 分钟。
题目:实现一个二叉搜索树迭代器。你将使用二叉搜索树的根节点初始化迭代器。
调用 next() 将返回二叉搜索树中的下一个最小的数。
题解一、对其进行遍历,存储
class TreeNode{ int val; TreeNode left; TreeNode right; TreeNode(int x){ val = x; } } class BSTIterator { int index; ArrayListlist; public BSTIterator(TreeNode root) { this.list = new ArrayList<>(); this.index = -1; this.inorder(root); } // 先进行中序遍历 private void inorder(TreeNode root){ if(root==null){ return; } inorder(root.left); list.add(root.val); inorder(root.right); } /** @return the next smallest number */ public int next() { return list.get(++index); } /** @return whether we have a next smallest number */ public boolean hasNext() { return this.index+1 < this.list.size(); } }
对其进行用栈来存储
class BSTIterator { // 栈 Stackstack; public BSTIterator(TreeNode root) { // 初始化 stack = new Stack<>(); this.pre(root); } // 先存储一部分值 private void pre(TreeNode root){ while(root!=null){ stack.push(root); root = root.left; } } /** @return the next smallest number */ public int next() { TreeNode temp = this.stack.pop(); if(temp.right!=null){ this.pre(temp.right); } return temp.val; } /** @return whether we have a next smallest number */ public boolean hasNext() { return this.stack.size()>0; } }
转载地址:https://codingchaozhang.blog.csdn.net/article/details/109497176 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
第一次来,支持一个
[***.219.124.196]2024年04月09日 13时18分57秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
PCB走线角度为90度到底行不行?
2019-04-29
这个 17 岁的黑客天才,破解了第一代 iPhone!
2019-04-29
在STM32价格疯长下,哪些国产32可以替代?
2019-04-29
半导体芯片原厂涨价及调价声明新增了这些!
2019-04-29
为什么你学C++这么难?
2019-04-29
无人机破巡检难题,秒变电网卫士
2019-04-29
五年,我成为了一名嵌入式工程师。
2019-04-29
2020年电赛题目,命题专家们怎么看?
2019-04-29
PCB元器件摆放不可忽略的10个技巧
2019-04-29
掌握AI核心技术没有秘籍,能自己创造就是王道
2019-04-29
大学老师的月薪多少?实话实说:4万多一点……
2019-04-29
2020年电赛题目,命题专家权威解析!
2019-04-29
如何掌握“所有”的程序语言?没错,就是所有!
2019-04-29
39岁单身程序员入住养老院
2019-04-29
写论文,这个神器不能少!
2019-04-29
我在哥大读博的五年,万字总结
2019-04-29
本科、硕士、博士,究竟有何区别?
2019-04-29
如果我的实验室也这样布置,那多好。
2019-04-29
现在做硬件工程师还有前途吗?
2019-04-29
用 50 种编程语言写“Hello,World!”
2019-04-29