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

【LeetCode-中等题】230. 二叉搜索树中第K小的元素

文章目录

    • 题目
    • 方法一:层序遍历 + 集合排序
    • 方法二:中序遍历(栈 或者 递归 )
    • 方法三(方法二改进):中序遍历(栈 )

题目

在这里插入图片描述

在这里插入图片描述

该题最大的特点就是这个树是二叉树:
在这里插入图片描述

所以,中序遍历对二叉树的遍历本身就是有序的

方法一:层序遍历 + 集合排序

思想很简单,就是通过层序遍历将节点都加到List集合中,然后调用 Collections.sort(list)排序后,找第k小的数list.get(k-1)

    public int kthSmallest(TreeNode root, int k) {List<Integer> list = levelOrder(root);Collections.sort(list);return list.get(k-1);}public List<Integer> levelOrder(TreeNode root) {List<Integer> result = new ArrayList<>();Queue<TreeNode> queue = new LinkedList<TreeNode>();if(root == null) return result;queue.offer(root);while(!queue.isEmpty()){int count = queue.size();for(int i =0 ;i< count ;i++){TreeNode node =   queue.poll();result.add(node.val); if(node.left != null)  queue.offer(node.left);if(node.right != null) queue.offer(node.right);}}return result;}

方法二:中序遍历(栈 或者 递归 )

二叉树中序遍历得到的值序列是递增有序的 借助一个list集合来接收有序的节点 然后再按照k去list集合区第k小的数

  List<Integer> list =new ArrayList<>();public int kthSmallest(TreeNode root, int k) {// dfs(root);    //递归中序stackTree(root); //  栈中序return list.get(k-1);}//递归中序//  public void dfs(TreeNode root) {//      if(root == null ) return ;//      dfs(root.left);//      list.add(root.val);//      dfs(root.right);//  }//  栈中序public void stackTree(TreeNode root) {Deque<TreeNode> stack = new ArrayDeque<TreeNode>();while(!stack.isEmpty() || root != null){while(root != null){stack.push(root);root = root.left;}root = stack.pop();list.add(root.val);root = root.right;}}

方法三(方法二改进):中序遍历(栈 )

二叉树中序遍历得到的值序列是递增有序的 那只要栈每次弹出一个元素时 就让k-1(直到k=0) 例如要第1小的数 那么其实就是中序遍历栈弹出的第一个元素(k= k-1 ===0,立马返回第一次pop的数)

    public int kthSmallest(TreeNode root, int k) {Deque<TreeNode> stack = new ArrayDeque<TreeNode>();while(!stack.isEmpty() || root != null){while(root != null){stack.push(root);root = root.left;}root = stack.pop();k--;//每弹出一个元素,就让k--if(k == 0) return root.val;//直到k减到0  说明该root.val就是第k小的数root = root.right;}return -1;}

相关文章:

【LeetCode-中等题】230. 二叉搜索树中第K小的元素

文章目录 题目方法一&#xff1a;层序遍历 集合排序方法二&#xff1a;中序遍历&#xff08;栈 或者 递归 &#xff09;方法三&#xff08;方法二改进&#xff09;&#xff1a;中序遍历&#xff08;栈 &#xff09; 题目 该题最大的特点就是这个树是二叉树&#xff1a; 所以…...

DQL语句的用法(MySQL)

文章目录 前言一、DQL语句间接和语法1、DQL简介2、DQL语法 二、DQL语句使用1、基础查询&#xff08;1&#xff09;查询多个字段&#xff08;2&#xff09;为字段设置别名&#xff08;3&#xff09;去除重复记录 总结 前言 本文主要介绍SQL语句中DQL语句的功能和使用方法&#…...

【Navicat Premium 16】使用Navicat将excel的数据进行单表的导入,详细操作

业务场景&#xff1a;经常与数据打交道嘛&#xff0c;有的时候会需要将excel的数据导入到数据库中&#xff0c;后面发现对于单表的数据导入&#xff0c;使用Navicat还是非常方便的&#xff0c;仅仅需要将字段关系映射好就可以了 一、开始操作 前提条件&#xff1a;已经成功连接…...

学习笔记230810--vue项目中get请求的两种传参方式

问题描述 今天写了一个对象方式传参的get请求接口方法&#xff0c;发现没有载荷&#xff0c;ip地址也没有带查询字符串&#xff0c;数据也没有响应。 代码展示 错误分析 实际上这里的query是对象方式带参跳转的参数名&#xff0c;而get方法对象方式传参的参数名是parmas 解…...

分享一种针对uni-app相对通用的抓包方案

PART1&#xff0c;前言 近年来混合开发APP逐渐成为主流的开发模式&#xff0c;与传统的开发模式相比混合开发极大的提升了开发效率&#xff0c;同时跨平台的特性也降低了开发成本&#xff0c;一直以来混合开发被诟病的性能问题随着技术的发展也得到改善。技术的发展往往是一把…...

【2023百度之星备赛】码蹄集 BD202301 公园(BFS求最短路)

题目 https://www.matiji.net/exam/brushquestion/1/4347/179CE77A7B772D15A8C00DD8198AAC74?from1 题目大意&#xff1a; 给定一个无向图&#xff0c;有两个人往同一个目的地走&#xff0c;分别消耗体力TE、FE。如果他们到某个点汇合了&#xff0c;然后一起走向目的地&…...

2022年下半年系统架构设计师真题(下午带答案)

试题一 (25分) 某电子商务公司拟升级其会员与促销管理系统&#xff0c;向用户提供个性化服务&#xff0c;提高用户的粘性。在项目立项之初&#xff0c;公司领导层一致认为本次升级的主要目标是提升会员管理方式的灵活性&#xff0c;由于当前用户规模不大&#xff0c;业务也相对…...

26、ADS瞬时波形仿真-TRANSIENT仿真(以共射放大器为例)

26、ADS瞬时波形仿真-TRANSIENT仿真&#xff08;以共射放大器为例&#xff09; 在本科期间&#xff0c;学习模电的时候总是要对各种三极管电路进行MULTISIM仿真&#xff0c;其实ADS具备相同的功能&#xff0c;而且对于射频电路&#xff0c;使用ADS进行仿真可以结合版图进行&am…...

【微服务部署】02-配置管理

文章目录 1.ConfigMap1.1 创建ConfigMap方式1.2 使用ConfigMap的方式1.3 ConfigMap使用要点建议 2 分布式配置中心解决方案2.1 什么时候选择配置中心2.2 Apollo配置中心系统的能力2.2.1 Apollo创建配置项目2.2.2 项目使用2.2.3 K8s中使用Apollo 1.ConfigMap ConfigMap是K8s提供…...

NTP时钟同步服务器

目录 一、什么是NTP&#xff1f; 二、计算机时间分类 三、NTP如何工作&#xff1f; 四、NTP时钟同步方式&#xff08;linux&#xff09; 五、时间同步实现软件&#xff08;既是客户端软件也是服务端软件&#xff09; 六、chrony时钟同步软件介绍 七、/etc/chrony.conf配置文件介…...

webassembly003 ggml GGML Tensor Library part-2 官方使用说明

https://github.com/ggerganov/whisper.cpp/tree/1.0.3 GGML Tensor Library 官方有一个函数使用说明&#xff0c;但是从初始版本就没修改过 : https://github1s.com/ggerganov/ggml/blob/master/include/ggml/ggml.h#L3-L173 This documentation is still a work in progres…...

ES主集群的优化参考点

因为流量比较大&#xff0c; 导致ES线程数飙高&#xff0c;cpu直往上窜&#xff0c;查询耗时增加&#xff0c;并传导给所有调用方&#xff0c;导致更大范围的延时。如何解决这个问题呢&#xff1f; ES负载不合理&#xff0c;热点问题严重。ES主集群一共有几十个节点&#xff0…...

全国范围内-二手房小区数据-2023-8月更新

收录融合去重多个平台数据&#xff1a;80万&#xff0c;仅供数字参考 数据纬度字段名注释枚举值基础信息id主键id&#xff1a;名称城市来源生成 md5值00001073838501125ec4473463ead9ccname名称瑞祥安文创园address地址(朝阳)双桥路东柳村口南口lng经度116.581903lat纬度39.89…...

第4章 循环变换

4.1 适配体系结构特征的关键技术 由于高级语言隐藏了底层硬件体系结构的大量细节&#xff0c;如果不经过优化直接将高级程序设计语言编写的程序部署在底层硬件上&#xff0c;往往无法充分利用底层硬件体系结构的处理能力。 算子融合不仅可以提…...

spring cloud使用git作为配置中心,git开启了双因子认证,如何写本地配置文件

问题 spring cloud使用git作为配置中心&#xff0c;git开启了双因子认证&#xff0c;死活认证不成功&#xff01;&#xff01;&#xff01;&#xff01;&#xff01; 报错关键字 org.eclipse.jgit.api.errors.TransportException: https://git.qualink.com/zhaoxin15/sc-confi…...

JVM内存管理、内存分区:堆、方法区、虚拟机栈、本地方法栈、程序计数器

内存管理 内存分区 线程共享 堆 存放实例&#xff0c;字符串常量&#xff08;直接引用&#xff09;&#xff0c;静态变量&#xff0c;线程分配缓冲区&#xff08;TLAB线程私有&#xff09;。垃圾收集器管理的区域 方法区 非堆&#xff0c;和堆相对的概念。存储已被虚拟机加载的…...

L1-047 装睡(Python实现) 测试点全过

题目 你永远叫不醒一个装睡的人 —— 但是通过分析一个人的呼吸频率和脉搏&#xff0c;你可以发现谁在装睡&#xff01;医生告诉我们&#xff0c;正常人睡眠时的呼吸频率是每分钟15-20次&#xff0c;脉搏是每分钟50-70次。下面给定一系列人的呼吸频率与脉搏&#xff0c;请你找…...

Mysql优化原理分析

一、存储引擎 1.1 MyISAM 一张表生成三个文件 xxx.frm&#xff1a;存储表结构xxx.MYD&#xff1a;存储表数据xxx.MYI&#xff1a;存储表索引 索引文件和数据文件是分离的&#xff08;非聚集&#xff09; select * from t where t.col1 30; 先去t.MYI文件查找30对应的索引…...

软考高级系统架构设计师系列案例考点专题一:软件架构设计

软考高级系统架构设计师系列案例考点专题一:软件架构设计 一、考点梳理及精讲1.质量属性判断与质量属性效用树2.必备概念3.架构风格对比4.MVC架构5.J2EE架构6.面向服务的架构SOA7.企业服务总线ESB一、考点梳理及精讲 系统架构设计师方面的知识在案例分析中每年必考1~2题,并且…...

css实现垂直上下布局的两种常用方法

例子&#xff1a;将两个<span>元素在<div>内垂直居中放置. 方法一&#xff1a;使用 Flexbox 来实现。 在下面的示例中&#xff0c;我将为 <div> 元素添加样式&#xff0c;使其成为一个 Flex 容器&#xff0c;并使用 Flexbox 属性将其中的两个 <span>…...

2024年赣州旅游投资集团社会招聘笔试真

2024年赣州旅游投资集团社会招聘笔试真 题 ( 满 分 1 0 0 分 时 间 1 2 0 分 钟 ) 一、单选题(每题只有一个正确答案,答错、不答或多答均不得分) 1.纪要的特点不包括()。 A.概括重点 B.指导传达 C. 客观纪实 D.有言必录 【答案】: D 2.1864年,()预言了电磁波的存在,并指出…...

Golang dig框架与GraphQL的完美结合

将 Go 的 Dig 依赖注入框架与 GraphQL 结合使用&#xff0c;可以显著提升应用程序的可维护性、可测试性以及灵活性。 Dig 是一个强大的依赖注入容器&#xff0c;能够帮助开发者更好地管理复杂的依赖关系&#xff0c;而 GraphQL 则是一种用于 API 的查询语言&#xff0c;能够提…...

Ascend NPU上适配Step-Audio模型

1 概述 1.1 简述 Step-Audio 是业界首个集语音理解与生成控制一体化的产品级开源实时语音对话系统&#xff0c;支持多语言对话&#xff08;如 中文&#xff0c;英文&#xff0c;日语&#xff09;&#xff0c;语音情感&#xff08;如 开心&#xff0c;悲伤&#xff09;&#x…...

NLP学习路线图(二十三):长短期记忆网络(LSTM)

在自然语言处理(NLP)领域,我们时刻面临着处理序列数据的核心挑战。无论是理解句子的结构、分析文本的情感,还是实现语言的翻译,都需要模型能够捕捉词语之间依时序产生的复杂依赖关系。传统的神经网络结构在处理这种序列依赖时显得力不从心,而循环神经网络(RNN) 曾被视为…...

聊一聊接口测试的意义有哪些?

目录 一、隔离性 & 早期测试 二、保障系统集成质量 三、验证业务逻辑的核心层 四、提升测试效率与覆盖度 五、系统稳定性的守护者 六、驱动团队协作与契约管理 七、性能与扩展性的前置评估 八、持续交付的核心支撑 接口测试的意义可以从四个维度展开&#xff0c;首…...

Rapidio门铃消息FIFO溢出机制

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

优选算法第十二讲:队列 + 宽搜 优先级队列

优选算法第十二讲&#xff1a;队列 宽搜 && 优先级队列 1.N叉树的层序遍历2.二叉树的锯齿型层序遍历3.二叉树最大宽度4.在每个树行中找最大值5.优先级队列 -- 最后一块石头的重量6.数据流中的第K大元素7.前K个高频单词8.数据流的中位数 1.N叉树的层序遍历 2.二叉树的锯…...

均衡后的SNRSINR

本文主要摘自参考文献中的前两篇&#xff0c;相关文献中经常会出现MIMO检测后的SINR不过一直没有找到相关数学推到过程&#xff0c;其中文献[1]中给出了相关原理在此仅做记录。 1. 系统模型 复信道模型 n t n_t nt​ 根发送天线&#xff0c; n r n_r nr​ 根接收天线的 MIMO 系…...

【Go语言基础【13】】函数、闭包、方法

文章目录 零、概述一、函数基础1、函数基础概念2、参数传递机制3、返回值特性3.1. 多返回值3.2. 命名返回值3.3. 错误处理 二、函数类型与高阶函数1. 函数类型定义2. 高阶函数&#xff08;函数作为参数、返回值&#xff09; 三、匿名函数与闭包1. 匿名函数&#xff08;Lambda函…...

jdbc查询mysql数据库时,出现id顺序错误的情况

我在repository中的查询语句如下所示&#xff0c;即传入一个List<intager>的数据&#xff0c;返回这些id的问题列表。但是由于数据库查询时ID列表的顺序与预期不一致&#xff0c;会导致返回的id是从小到大排列的&#xff0c;但我不希望这样。 Query("SELECT NEW com…...