当前位置: 首页 > news >正文

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 操作

三、解题思路

  1. 基本思路:
      初看题目,无非递归和栈两种做法。再看进阶时, O ( h ) \Omicron(h) O(h) 的空间复杂度实现 O ( 1 ) \Omicron(1) O(1) 的 next ,想了半天,没有想出来是怎么实现的,最后就用栈实现,然后去看官方题解是怎么实现的,结果也是用栈,看了复杂度分析,好家伙,搁着搞平均是吧!
    官方题解截图:
    在这里插入图片描述
  2. 具体思路:
    • 创建一个栈,初始化依次把根节点到最左节点压入栈;
    • 每次调用 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 &#xff0c;表示一个按中序遍历二叉搜索树&#xff08;BST&#xff09;的迭代器&#xff1a; BSTIterato…...

大三学生实习面试经历(1)

最近听了一位学长的建议&#xff0c;不能等一切都准备好再去开始&#xff0c;于是就开始了简历投递&#xff0c;恰好简历过了某小厂的初筛&#xff0c;开启了线上面试&#xff0c;记录了一些问题&#xff1a; &#xff08;通过面试也确实了解到了自己在某些方面确实做的还不够…...

【论文复现】STM32设计的物联网智能鱼缸

&#x1f4dd;个人主页&#x1f339;&#xff1a;Eternity._ &#x1f339;&#x1f339;期待您的关注 &#x1f339;&#x1f339; ❀STM32设计的物联网智能鱼缸 【1】项目功能介绍【2】设计需求总结【3】项目硬件模块组成 1.2 设计思路【1】整体设计思路【2】ESP8266工作模式…...

常见长选项和短选项对应表

长选项和短选项的等效形式 在命令行工具中&#xff0c;这种长选项&#xff08;如--delete&#xff09;和短选项&#xff08;如-d&#xff09;等效的情况很常见。例如--verbose和-v&#xff08;用于输出详细信息&#xff09;&#xff0c;--quiet和-q&#xff08;用于安静模式&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认证与令牌桶算法 在现代后端开发中&#xff0c;用户认证和接口限流是确保系统安全性和性能的两大关键要素…...

关于强化学习的一份介绍

在这篇文章中&#xff0c;我将介绍与强化学习有关的一些东西&#xff0c;具体包括相关概念、k-摇臂机、强化学习的种类等。 一、基本概念 所谓强化学习就是去学习&#xff1a;做什么才能使得数值化的收益信号最大化。学习者不会被告知应该采取什么动作&#xff0c;而是必须通…...

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、事件队列&#xff1a;异步的处理&#xff0c;按顺序执行 import package:flutter/material.dart; main(){testFuture1();testFuture2(); }// 按顺序执行处理A->B->C testFuture1() async {Future((){return 任务A;}).then((value){print(按顺序执行&…...

从零开始学习 sg200x 多核开发之 eth0 自动使能并配置静态IP

前文提到 sophpi 默认没有使能有线网络&#xff0c;需要手工配置&#xff1a; [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&#xff1a;进程间通信 《TCP/IP网络编程》学习笔记 | Chapter 11&#xff1a;进程间通信进程间通信的基本概念通过管道实现进程间通信通过管道进行进程间双向通信 运用进程间通信习题&#xff08;1&#xff09;什么是进程间通信&…...

开源模型应用落地-qwen模型小试-Qwen2.5-7B-Instruct-tool usage入门-集成心知天气(二)

一、前言 Qwen-Agent 是一个利用开源语言模型Qwen的工具使用、规划和记忆功能的框架。其模块化设计允许开发人员创建具有特定功能的定制代理,为各种应用程序提供了坚实的基础。同时,开发者可以利用 Qwen-Agent 的原子组件构建智能代理,以理解和响应用户查询。 本篇将介绍如何…...

通过声纹或者声波来切分一段音频

通过声纹识别或基于声波特征的模型&#xff0c;确实可以帮助切分一段音频并区分出不同讲话者的语音片段。这种技术被称为 基于声纹的语音分割 或 基于说话人识别的音频分割。其核心原理是利用每个说话者的 声纹特征&#xff08;即每个人独特的语音特征&#xff09;来识别和切分…...

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 ] 网络安全发展现状

&#x1f36c; 博主介绍 &#x1f468;‍&#x1f393; 博主介绍&#xff1a;大家好&#xff0c;我是 _PowerShell &#xff0c;很高兴认识大家~ ✨主攻领域&#xff1a;【渗透领域】【数据通信】 【通讯安全】 【web安全】【面试分析】 &#x1f389;点赞➕评论➕收藏 养成习…...

《基于Oracle的SQL优化》读书笔记

查看执行计划set autotrace traceonly explain在当前session中将优化器模式改为RULE。alter session set optimizer_modeRULE;统计信息存储在oracle的数据字典里&#xff0c;且从多个维度描述了oracle数据库里相关对象的实际数据量&#xff0c;实际数据分布等详细信息。 -- 对…...

零基础利用实战项目学会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 三行搞定&#xff01; 4.5 准确率 5、Pytorch完成回归任务 5.…...

Go八股(Ⅵ)Goroutine 以及其中的锁和思想

Goroutine与并发编程的关系 什么是并发 是指多个任务在同一时间段内进行处理&#xff0c;但不一定是在同一时刻执行。并发强调的是“结构上的并行性”&#xff0c;也就是说&#xff0c;程序能够在一个时间端内同时处理多个任务&#xff0c;但是这些任务可能是交替进行的。例如…...

向潜在安全信息和事件管理 SIEM 提供商提出的六个问题

收集和解读数据洞察以制定可用的解决方案是强大网络安全策略的基础。然而&#xff0c;组织正淹没在数据中&#xff0c;这使得这项任务变得复杂。 传统的安全信息和事件管理 ( SIEM ) 工具是组织尝试使用的一种方法&#xff0c;但由于成本、资源和可扩展性等几个原因&#xff0…...

蓝桥杯每日真题 - 第15天

题目&#xff1a;&#xff08;钟表&#xff09; 题目描述&#xff08;13届 C&C B组B题&#xff09; 解题思路&#xff1a; 理解钟表指针的运动&#xff1a; 秒针每分钟转一圈&#xff0c;即每秒转6度。 分针每小时转一圈&#xff0c;即每分钟转6度。 时针每12小时转一圈…...

synchronized 学习

学习源&#xff1a; https://www.bilibili.com/video/BV1aJ411V763?spm_id_from333.788.videopod.episodes&vd_source32e1c41a9370911ab06d12fbc36c4ebc 1.应用场景 不超卖&#xff0c;也要考虑性能问题&#xff08;场景&#xff09; 2.常见面试问题&#xff1a; sync出…...

51c自动驾驶~合集58

我自己的原文哦~ https://blog.51cto.com/whaosoft/13967107 #CCA-Attention 全局池化局部保留&#xff0c;CCA-Attention为LLM长文本建模带来突破性进展 琶洲实验室、华南理工大学联合推出关键上下文感知注意力机制&#xff08;CCA-Attention&#xff09;&#xff0c;…...

反向工程与模型迁移:打造未来商品详情API的可持续创新体系

在电商行业蓬勃发展的当下&#xff0c;商品详情API作为连接电商平台与开发者、商家及用户的关键纽带&#xff0c;其重要性日益凸显。传统商品详情API主要聚焦于商品基本信息&#xff08;如名称、价格、库存等&#xff09;的获取与展示&#xff0c;已难以满足市场对个性化、智能…...

Java-41 深入浅出 Spring - 声明式事务的支持 事务配置 XML模式 XML+注解模式

点一下关注吧&#xff01;&#xff01;&#xff01;非常感谢&#xff01;&#xff01;持续更新&#xff01;&#xff01;&#xff01; &#x1f680; AI篇持续更新中&#xff01;&#xff08;长期更新&#xff09; 目前2025年06月05日更新到&#xff1a; AI炼丹日志-28 - Aud…...

NFT模式:数字资产确权与链游经济系统构建

NFT模式&#xff1a;数字资产确权与链游经济系统构建 ——从技术架构到可持续生态的范式革命 一、确权技术革新&#xff1a;构建可信数字资产基石 1. 区块链底层架构的进化 跨链互操作协议&#xff1a;基于LayerZero协议实现以太坊、Solana等公链资产互通&#xff0c;通过零知…...

Rapidio门铃消息FIFO溢出机制

关于RapidIO门铃消息FIFO的溢出机制及其与中断抖动的关系&#xff0c;以下是深入解析&#xff1a; 门铃FIFO溢出的本质 在RapidIO系统中&#xff0c;门铃消息FIFO是硬件控制器内部的缓冲区&#xff0c;用于临时存储接收到的门铃消息&#xff08;Doorbell Message&#xff09;。…...

企业如何增强终端安全?

在数字化转型加速的今天&#xff0c;企业的业务运行越来越依赖于终端设备。从员工的笔记本电脑、智能手机&#xff0c;到工厂里的物联网设备、智能传感器&#xff0c;这些终端构成了企业与外部世界连接的 “神经末梢”。然而&#xff0c;随着远程办公的常态化和设备接入的爆炸式…...

Springboot社区养老保险系统小程序

一、前言 随着我国经济迅速发展&#xff0c;人们对手机的需求越来越大&#xff0c;各种手机软件也都在被广泛应用&#xff0c;但是对于手机进行数据信息管理&#xff0c;对于手机的各种软件也是备受用户的喜爱&#xff0c;社区养老保险系统小程序被用户普遍使用&#xff0c;为方…...

智能AI电话机器人系统的识别能力现状与发展水平

一、引言 随着人工智能技术的飞速发展&#xff0c;AI电话机器人系统已经从简单的自动应答工具演变为具备复杂交互能力的智能助手。这类系统结合了语音识别、自然语言处理、情感计算和机器学习等多项前沿技术&#xff0c;在客户服务、营销推广、信息查询等领域发挥着越来越重要…...

LabVIEW双光子成像系统技术

双光子成像技术的核心特性 双光子成像通过双低能量光子协同激发机制&#xff0c;展现出显著的技术优势&#xff1a; 深层组织穿透能力&#xff1a;适用于活体组织深度成像 高分辨率观测性能&#xff1a;满足微观结构的精细研究需求 低光毒性特点&#xff1a;减少对样本的损伤…...