173. 二叉搜索树迭代器【 力扣(LeetCode) 】
文章目录
- 零、原题链接
- 一、题目描述
- 二、测试用例
- 三、解题思路
- 四、参考代码
零、原题链接
173. 二叉搜索树迭代器
一、题目描述
实现一个二叉搜索树迭代器类BSTIterator ,表示一个按中序遍历二叉搜索树(BST)的迭代器:
BSTIterator(TreeNode root) 初始化 BSTIterator 类的一个对象。BST 的根节点 root 会作为构造函数的一部分给出。指针应初始化为一个不存在于 BST 中的数字,且该数字小于 BST 中的任何元素。
boolean hasNext() 如果向指针右侧遍历存在数字,则返回 true ;否则返回 false 。
int next()将指针向右移动,然后返回指针处的数字。
注意,指针初始化为一个不存在于 BST 中的数字,所以对 next() 的首次调用将返回 BST 中的最小元素。
你可以假设 next() 调用总是有效的,也就是说,当调用 next() 时,BST 的中序遍历中至少存在一个下一个数字。
进阶:
你可以设计一个满足下述条件的解决方案吗?next() 和 hasNext() 操作均摊时间复杂度为 O(1) ,并使用 O(h) 内存。其中 h 是树的高度。
二、测试用例
示例:

输入
["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 操作
三、解题思路
- 基本思路:
初看题目,无非递归和栈两种做法。再看进阶时, O ( h ) \Omicron(h) O(h) 的空间复杂度实现 O ( 1 ) \Omicron(1) O(1) 的 next ,想了半天,没有想出来是怎么实现的,最后就用栈实现,然后去看官方题解是怎么实现的,结果也是用栈,看了复杂度分析,好家伙,搁着搞平均是吧!
官方题解截图:

- 具体思路:
- 创建一个栈,初始化依次把根节点到最左节点压入栈;
- 每次调用 next ,则出栈一个元素;并依次将该元素右子树根到其最左节点压入栈;
- 调用 hasNext ,就返回栈的大小;
四、参考代码
时间复杂度: O ( n ) \Omicron(n) O(n)
空间复杂度: O ( h ) \Omicron(h) O(h)
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),* right(right) {}* };*/
class BSTIterator {
public:vector<TreeNode*> s;BSTIterator(TreeNode* root) {for (TreeNode* p = root; p; p = p->left)s.emplace_back(p);}int next() {TreeNode* t = s.back();s.pop_back();for (TreeNode* p = t->right; p; p = p->left)s.emplace_back(p);return t->val;}bool hasNext() { return s.size(); }
};/*** Your BSTIterator object will be instantiated and called as such:* BSTIterator* obj = new BSTIterator(root);* int param_1 = obj->next();* bool param_2 = obj->hasNext();*/
相关文章:
173. 二叉搜索树迭代器【 力扣(LeetCode) 】
文章目录 零、原题链接一、题目描述二、测试用例三、解题思路四、参考代码 零、原题链接 173. 二叉搜索树迭代器 一、题目描述 实现一个二叉搜索树迭代器类BSTIterator ,表示一个按中序遍历二叉搜索树(BST)的迭代器: BSTIterato…...
大三学生实习面试经历(1)
最近听了一位学长的建议,不能等一切都准备好再去开始,于是就开始了简历投递,恰好简历过了某小厂的初筛,开启了线上面试,记录了一些问题: (通过面试也确实了解到了自己在某些方面确实做的还不够…...
【论文复现】STM32设计的物联网智能鱼缸
📝个人主页🌹:Eternity._ 🌹🌹期待您的关注 🌹🌹 ❀STM32设计的物联网智能鱼缸 【1】项目功能介绍【2】设计需求总结【3】项目硬件模块组成 1.2 设计思路【1】整体设计思路【2】ESP8266工作模式…...
常见长选项和短选项对应表
长选项和短选项的等效形式 在命令行工具中,这种长选项(如--delete)和短选项(如-d)等效的情况很常见。例如--verbose和-v(用于输出详细信息),--quiet和-q(用于安静模式&a…...
Ubuntu24 上安装搜狗输入法
link 首先在终端中依次输入以下代码 sudo apt update sudo apt install fcitx 找到语言支持 在终端中依次输入 sudo cp /usr/share/applications/fcitx.desktop /etc/xdg/autostart/ sudo apt purge ibus 进入网页 搜狗输入法linux-首页 shurufa.sogou.com/linux 找到刚才下…...
【AI图像生成网站Golang】JWT认证与令牌桶算法
AI图像生成网站 目录 一、项目介绍 二、雪花算法 三、JWT认证与令牌桶算法 四、项目架构 五、图床上传与图像生成API搭建 六、项目测试与调试(等待更新) 三、JWT认证与令牌桶算法 在现代后端开发中,用户认证和接口限流是确保系统安全性和性能的两大关键要素…...
关于强化学习的一份介绍
在这篇文章中,我将介绍与强化学习有关的一些东西,具体包括相关概念、k-摇臂机、强化学习的种类等。 一、基本概念 所谓强化学习就是去学习:做什么才能使得数值化的收益信号最大化。学习者不会被告知应该采取什么动作,而是必须通…...
Python3.11.9+selenium,获取图片验证码以及输入验证码数字
Python3.11.9+selenium,获取图片验证码以及输入验证码数字 1、遇到问题:登录或修改密码需要验证码 2、解决办法: 2.1、安装ddddocr pip install ddddocr 2.2、解析验证码函数 import ddddocr def get_capcha_text():#获取验证码图片ele_pic = driver.find_element(By.XPAT…...
Flutter:事件队列,异步操作,链式调用。
Flutter分2种队列 1、事件队列:异步的处理,按顺序执行 import package:flutter/material.dart; main(){testFuture1();testFuture2(); }// 按顺序执行处理A->B->C testFuture1() async {Future((){return 任务A;}).then((value){print(按顺序执行&…...
从零开始学习 sg200x 多核开发之 eth0 自动使能并配置静态IP
前文提到 sophpi 默认没有使能有线网络,需要手工配置: [rootsg200x]~# ifconfig eth0 up [rootsg200x]~# udhcpc -i eth0 [rootsg200x]~# ifconfig eth0 Link encap:Ethernet HWaddr EA:BD:18:08:1E:87 inet addr:192.168.188.142 Bcast:192.1…...
《TCP/IP网络编程》学习笔记 | Chapter 11:进程间通信
《TCP/IP网络编程》学习笔记 | Chapter 11:进程间通信 《TCP/IP网络编程》学习笔记 | Chapter 11:进程间通信进程间通信的基本概念通过管道实现进程间通信通过管道进行进程间双向通信 运用进程间通信习题(1)什么是进程间通信&…...
开源模型应用落地-qwen模型小试-Qwen2.5-7B-Instruct-tool usage入门-集成心知天气(二)
一、前言 Qwen-Agent 是一个利用开源语言模型Qwen的工具使用、规划和记忆功能的框架。其模块化设计允许开发人员创建具有特定功能的定制代理,为各种应用程序提供了坚实的基础。同时,开发者可以利用 Qwen-Agent 的原子组件构建智能代理,以理解和响应用户查询。 本篇将介绍如何…...
通过声纹或者声波来切分一段音频
通过声纹识别或基于声波特征的模型,确实可以帮助切分一段音频并区分出不同讲话者的语音片段。这种技术被称为 基于声纹的语音分割 或 基于说话人识别的音频分割。其核心原理是利用每个说话者的 声纹特征(即每个人独特的语音特征)来识别和切分…...
sql专场练习(二)(16-20)完结
第十六题 用户登录日志表为user_id,log_id,session_id,visit_time create table sql2_16(user_id int,log_id int,session_id int,visit_time string );没有数据 visit_time 时间格式为2024-11-15 用sql查询近30天每天平均登录用户数量 with t1 as (select visit_time,coun…...
[ 网络安全介绍 2 ] 网络安全发展现状
🍬 博主介绍 👨🎓 博主介绍:大家好,我是 _PowerShell ,很高兴认识大家~ ✨主攻领域:【渗透领域】【数据通信】 【通讯安全】 【web安全】【面试分析】 🎉点赞➕评论➕收藏 养成习…...
《基于Oracle的SQL优化》读书笔记
查看执行计划set autotrace traceonly explain在当前session中将优化器模式改为RULE。alter session set optimizer_modeRULE;统计信息存储在oracle的数据字典里,且从多个维度描述了oracle数据库里相关对象的实际数据量,实际数据分布等详细信息。 -- 对…...
零基础利用实战项目学会Pytorch
目录 pytorch简介 1.线性回归 2.数据类型 2.1数据类型检验 2.2Dimension0/Rank0 2.3 Dim1/Rank1 2.4 Dim2/Rank2 3.一些方法 4.Pytorch完成分类任务 4.1模型参数 4.2 前向传播 4.3训练以及验证 4.4 三行搞定! 4.5 准确率 5、Pytorch完成回归任务 5.…...
Go八股(Ⅵ)Goroutine 以及其中的锁和思想
Goroutine与并发编程的关系 什么是并发 是指多个任务在同一时间段内进行处理,但不一定是在同一时刻执行。并发强调的是“结构上的并行性”,也就是说,程序能够在一个时间端内同时处理多个任务,但是这些任务可能是交替进行的。例如…...
向潜在安全信息和事件管理 SIEM 提供商提出的六个问题
收集和解读数据洞察以制定可用的解决方案是强大网络安全策略的基础。然而,组织正淹没在数据中,这使得这项任务变得复杂。 传统的安全信息和事件管理 ( SIEM ) 工具是组织尝试使用的一种方法,但由于成本、资源和可扩展性等几个原因࿰…...
蓝桥杯每日真题 - 第15天
题目:(钟表) 题目描述(13届 C&C B组B题) 解题思路: 理解钟表指针的运动: 秒针每分钟转一圈,即每秒转6度。 分针每小时转一圈,即每分钟转6度。 时针每12小时转一圈…...
web vue 项目 Docker化部署
Web 项目 Docker 化部署详细教程 目录 Web 项目 Docker 化部署概述Dockerfile 详解 构建阶段生产阶段 构建和运行 Docker 镜像 1. Web 项目 Docker 化部署概述 Docker 化部署的主要步骤分为以下几个阶段: 构建阶段(Build Stage):…...
谷歌浏览器插件
项目中有时候会用到插件 sync-cookie-extension1.0.0:开发环境同步测试 cookie 至 localhost,便于本地请求服务携带 cookie 参考地址:https://juejin.cn/post/7139354571712757767 里面有源码下载下来,加在到扩展即可使用FeHelp…...
stm32G473的flash模式是单bank还是双bank?
今天突然有人stm32G473的flash模式是单bank还是双bank?由于时间太久,我真忘记了。搜搜发现,还真有人和我一样。见下面的链接:https://shequ.stmicroelectronics.cn/forum.php?modviewthread&tid644563 根据STM32G4系列参考手…...
day52 ResNet18 CBAM
在深度学习的旅程中,我们不断探索如何提升模型的性能。今天,我将分享我在 ResNet18 模型中插入 CBAM(Convolutional Block Attention Module)模块,并采用分阶段微调策略的实践过程。通过这个过程,我不仅提升…...
可靠性+灵活性:电力载波技术在楼宇自控中的核心价值
可靠性灵活性:电力载波技术在楼宇自控中的核心价值 在智能楼宇的自动化控制中,电力载波技术(PLC)凭借其独特的优势,正成为构建高效、稳定、灵活系统的核心解决方案。它利用现有电力线路传输数据,无需额外布…...
多模态商品数据接口:融合图像、语音与文字的下一代商品详情体验
一、多模态商品数据接口的技术架构 (一)多模态数据融合引擎 跨模态语义对齐 通过Transformer架构实现图像、语音、文字的语义关联。例如,当用户上传一张“蓝色连衣裙”的图片时,接口可自动提取图像中的颜色(RGB值&…...
Linux云原生安全:零信任架构与机密计算
Linux云原生安全:零信任架构与机密计算 构建坚不可摧的云原生防御体系 引言:云原生安全的范式革命 随着云原生技术的普及,安全边界正在从传统的网络边界向工作负载内部转移。Gartner预测,到2025年,零信任架构将成为超…...
听写流程自动化实践,轻量级教育辅助
随着智能教育工具的发展,越来越多的传统学习方式正在被数字化、自动化所优化。听写作为语文、英语等学科中重要的基础训练形式,也迎来了更高效的解决方案。 这是一款轻量但功能强大的听写辅助工具。它是基于本地词库与可选在线语音引擎构建,…...
React---day11
14.4 react-redux第三方库 提供connect、thunk之类的函数 以获取一个banner数据为例子 store: 我们在使用异步的时候理应是要使用中间件的,但是configureStore 已经自动集成了 redux-thunk,注意action里面要返回函数 import { configureS…...
高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数
高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数 在软件开发中,单例模式(Singleton Pattern)是一种常见的设计模式,确保一个类仅有一个实例,并提供一个全局访问点。在多线程环境下,实现单例模式时需要注意线程安全问题,以防止多个线程同时创建实例,导致…...
