【Leetcode刷题篇】leetcode173 二叉搜索树迭代器
发布日期:2021-06-29 15:33:27
浏览次数:3
分类:技术文章
本文共 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 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
很好
[***.229.124.182]2024年04月10日 22时45分18秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
一、UML图
2019-04-29
王爽汇编语言第三版答案
2019-04-29
C++类对象的大小(1)
2019-04-29
静态成员函数和非静态成员函数的区别
2019-04-29
C++类默认函数
2019-04-29
成员函数初始化列表
2019-04-29
FALSE/TRUE与false/true的区别
2019-04-29
const在函数前后的意义
2019-04-29
八、桥接模式
2019-04-29
五、状态模式
2019-04-29
设计模式-前言
2019-04-29
二、设计模式的基本原则
2019-04-29
四、观察者模式
2019-04-29
二十三、命令模式
2019-04-29
抽象工厂模式(22)
2019-04-29
工厂模式(21)
2019-04-29
原型模式(16)
2019-04-29
组合模式(17)
2019-04-29
备忘录模式(18)
2019-04-29
享元模式(19)
2019-04-29