【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小的元素
文章目录 题目方法一:层序遍历 集合排序方法二:中序遍历(栈 或者 递归 )方法三(方法二改进):中序遍历(栈 ) 题目 该题最大的特点就是这个树是二叉树: 所以…...
DQL语句的用法(MySQL)
文章目录 前言一、DQL语句间接和语法1、DQL简介2、DQL语法 二、DQL语句使用1、基础查询(1)查询多个字段(2)为字段设置别名(3)去除重复记录 总结 前言 本文主要介绍SQL语句中DQL语句的功能和使用方法&#…...
【Navicat Premium 16】使用Navicat将excel的数据进行单表的导入,详细操作
业务场景:经常与数据打交道嘛,有的时候会需要将excel的数据导入到数据库中,后面发现对于单表的数据导入,使用Navicat还是非常方便的,仅仅需要将字段关系映射好就可以了 一、开始操作 前提条件:已经成功连接…...
学习笔记230810--vue项目中get请求的两种传参方式
问题描述 今天写了一个对象方式传参的get请求接口方法,发现没有载荷,ip地址也没有带查询字符串,数据也没有响应。 代码展示 错误分析 实际上这里的query是对象方式带参跳转的参数名,而get方法对象方式传参的参数名是parmas 解…...
分享一种针对uni-app相对通用的抓包方案
PART1,前言 近年来混合开发APP逐渐成为主流的开发模式,与传统的开发模式相比混合开发极大的提升了开发效率,同时跨平台的特性也降低了开发成本,一直以来混合开发被诟病的性能问题随着技术的发展也得到改善。技术的发展往往是一把…...
【2023百度之星备赛】码蹄集 BD202301 公园(BFS求最短路)
题目 https://www.matiji.net/exam/brushquestion/1/4347/179CE77A7B772D15A8C00DD8198AAC74?from1 题目大意: 给定一个无向图,有两个人往同一个目的地走,分别消耗体力TE、FE。如果他们到某个点汇合了,然后一起走向目的地&…...
2022年下半年系统架构设计师真题(下午带答案)
试题一 (25分) 某电子商务公司拟升级其会员与促销管理系统,向用户提供个性化服务,提高用户的粘性。在项目立项之初,公司领导层一致认为本次升级的主要目标是提升会员管理方式的灵活性,由于当前用户规模不大,业务也相对…...
26、ADS瞬时波形仿真-TRANSIENT仿真(以共射放大器为例)
26、ADS瞬时波形仿真-TRANSIENT仿真(以共射放大器为例) 在本科期间,学习模电的时候总是要对各种三极管电路进行MULTISIM仿真,其实ADS具备相同的功能,而且对于射频电路,使用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? 二、计算机时间分类 三、NTP如何工作? 四、NTP时钟同步方式(linux) 五、时间同步实现软件(既是客户端软件也是服务端软件) 六、chrony时钟同步软件介绍 七、/etc/chrony.conf配置文件介…...
webassembly003 ggml GGML Tensor Library part-2 官方使用说明
https://github.com/ggerganov/whisper.cpp/tree/1.0.3 GGML Tensor Library 官方有一个函数使用说明,但是从初始版本就没修改过 : https://github1s.com/ggerganov/ggml/blob/master/include/ggml/ggml.h#L3-L173 This documentation is still a work in progres…...
ES主集群的优化参考点
因为流量比较大, 导致ES线程数飙高,cpu直往上窜,查询耗时增加,并传导给所有调用方,导致更大范围的延时。如何解决这个问题呢? ES负载不合理,热点问题严重。ES主集群一共有几十个节点࿰…...
全国范围内-二手房小区数据-2023-8月更新
收录融合去重多个平台数据:80万,仅供数字参考 数据纬度字段名注释枚举值基础信息id主键id:名称城市来源生成 md5值00001073838501125ec4473463ead9ccname名称瑞祥安文创园address地址(朝阳)双桥路东柳村口南口lng经度116.581903lat纬度39.89…...
第4章 循环变换
4.1 适配体系结构特征的关键技术 由于高级语言隐藏了底层硬件体系结构的大量细节,如果不经过优化直接将高级程序设计语言编写的程序部署在底层硬件上,往往无法充分利用底层硬件体系结构的处理能力。 算子融合不仅可以提…...
spring cloud使用git作为配置中心,git开启了双因子认证,如何写本地配置文件
问题 spring cloud使用git作为配置中心,git开启了双因子认证,死活认证不成功!!!!! 报错关键字 org.eclipse.jgit.api.errors.TransportException: https://git.qualink.com/zhaoxin15/sc-confi…...
JVM内存管理、内存分区:堆、方法区、虚拟机栈、本地方法栈、程序计数器
内存管理 内存分区 线程共享 堆 存放实例,字符串常量(直接引用),静态变量,线程分配缓冲区(TLAB线程私有)。垃圾收集器管理的区域 方法区 非堆,和堆相对的概念。存储已被虚拟机加载的…...
L1-047 装睡(Python实现) 测试点全过
题目 你永远叫不醒一个装睡的人 —— 但是通过分析一个人的呼吸频率和脉搏,你可以发现谁在装睡!医生告诉我们,正常人睡眠时的呼吸频率是每分钟15-20次,脉搏是每分钟50-70次。下面给定一系列人的呼吸频率与脉搏,请你找…...
Mysql优化原理分析
一、存储引擎 1.1 MyISAM 一张表生成三个文件 xxx.frm:存储表结构xxx.MYD:存储表数据xxx.MYI:存储表索引 索引文件和数据文件是分离的(非聚集) select * from t where t.col1 30; 先去t.MYI文件查找30对应的索引…...
软考高级系统架构设计师系列案例考点专题一:软件架构设计
软考高级系统架构设计师系列案例考点专题一:软件架构设计 一、考点梳理及精讲1.质量属性判断与质量属性效用树2.必备概念3.架构风格对比4.MVC架构5.J2EE架构6.面向服务的架构SOA7.企业服务总线ESB一、考点梳理及精讲 系统架构设计师方面的知识在案例分析中每年必考1~2题,并且…...
css实现垂直上下布局的两种常用方法
例子:将两个<span>元素在<div>内垂直居中放置. 方法一:使用 Flexbox 来实现。 在下面的示例中,我将为 <div> 元素添加样式,使其成为一个 Flex 容器,并使用 Flexbox 属性将其中的两个 <span>…...
UE5 学习系列(二)用户操作界面及介绍
这篇博客是 UE5 学习系列博客的第二篇,在第一篇的基础上展开这篇内容。博客参考的 B 站视频资料和第一篇的链接如下: 【Note】:如果你已经完成安装等操作,可以只执行第一篇博客中 2. 新建一个空白游戏项目 章节操作,重…...
CTF show Web 红包题第六弹
提示 1.不是SQL注入 2.需要找关键源码 思路 进入页面发现是一个登录框,很难让人不联想到SQL注入,但提示都说了不是SQL注入,所以就不往这方面想了 先查看一下网页源码,发现一段JavaScript代码,有一个关键类ctfs…...
Linux相关概念和易错知识点(42)(TCP的连接管理、可靠性、面临复杂网络的处理)
目录 1.TCP的连接管理机制(1)三次握手①握手过程②对握手过程的理解 (2)四次挥手(3)握手和挥手的触发(4)状态切换①挥手过程中状态的切换②握手过程中状态的切换 2.TCP的可靠性&…...
前端导出带有合并单元格的列表
// 导出async function exportExcel(fileName "共识调整.xlsx") {// 所有数据const exportData await getAllMainData();// 表头内容let fitstTitleList [];const secondTitleList [];allColumns.value.forEach(column > {if (!column.children) {fitstTitleL…...
如何在看板中有效管理突发紧急任务
在看板中有效管理突发紧急任务需要:设立专门的紧急任务通道、重新调整任务优先级、保持适度的WIP(Work-in-Progress)弹性、优化任务处理流程、提高团队应对突发情况的敏捷性。其中,设立专门的紧急任务通道尤为重要,这能…...
在Ubuntu中设置开机自动运行(sudo)指令的指南
在Ubuntu系统中,有时需要在系统启动时自动执行某些命令,特别是需要 sudo权限的指令。为了实现这一功能,可以使用多种方法,包括编写Systemd服务、配置 rc.local文件或使用 cron任务计划。本文将详细介绍这些方法,并提供…...
Axios请求超时重发机制
Axios 超时重新请求实现方案 在 Axios 中实现超时重新请求可以通过以下几种方式: 1. 使用拦截器实现自动重试 import axios from axios;// 创建axios实例 const instance axios.create();// 设置超时时间 instance.defaults.timeout 5000;// 最大重试次数 cons…...
Java面试专项一-准备篇
一、企业简历筛选规则 一般企业的简历筛选流程:首先由HR先筛选一部分简历后,在将简历给到对应的项目负责人后再进行下一步的操作。 HR如何筛选简历 例如:Boss直聘(招聘方平台) 直接按照条件进行筛选 例如:…...
Pinocchio 库详解及其在足式机器人上的应用
Pinocchio 库详解及其在足式机器人上的应用 Pinocchio (Pinocchio is not only a nose) 是一个开源的 C 库,专门用于快速计算机器人模型的正向运动学、逆向运动学、雅可比矩阵、动力学和动力学导数。它主要关注效率和准确性,并提供了一个通用的框架&…...
Android第十三次面试总结(四大 组件基础)
Activity生命周期和四大启动模式详解 一、Activity 生命周期 Activity 的生命周期由一系列回调方法组成,用于管理其创建、可见性、焦点和销毁过程。以下是核心方法及其调用时机: onCreate() 调用时机:Activity 首次创建时调用。…...
