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

LeetCode--HOT100题(44)

目录

  • 题目描述:230. 二叉搜索树中第K小的元素(中等)
    • 题目接口
    • 解题思路
    • 代码
  • PS:

题目描述:230. 二叉搜索树中第K小的元素(中等)

给定一个二叉搜索树的根节点 root ,和一个整数 k ,请你设计一个算法查找其中第 k 个最小元素(从 1 开始计数)。

LeetCode做题链接:LeetCode-两数之和

示例 1:
在这里插入图片描述

输入:root = [3,1,4,null,2], k = 1
输出:1

示例 2:
在这里插入图片描述

输入:root = [5,3,6,2,4,null,null,1], k = 3
输出:3

提示:

树中的节点数为 n 。
1 <= k <= n <= 104
0 <= Node.val <= 104

进阶: 如果二叉搜索树经常被修改(插入/删除操作)并且你需要频繁地查找第 k 小的值,你将如何优化算法?

题目接口

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public int kthSmallest(TreeNode root, int k) {}
}

解题思路

  1. 创建一个ArrayList用于存储中序遍历的结果。中序遍历是一种二叉树的遍历方式,顺序为左子树-根节点-右子树。这种遍历方式可以得到一个升序的序列。
  2. 定义一个方法kthSmallest,输入参数为二叉树的根节点和整数k,返回二叉树中第k小的元素。在这个方法中,首先调用dfs方法对二叉树进行中序遍历,将结果存储在list中。然后返回list中第k-1个元素,因为数组下标从0开始,而题目要求的k是从1开始的。
  3. 定义一个方法dfs,输入参数为二叉树的节点,递归地对该节点的左子树和右子树进行中序遍历。在这个方法中,首先判断当前节点是否为空,如果为空则直接返回。然后递归地对左子树进行中序遍历,将遍历得到的结果存储在list中。接着将当前节点的值添加到list中,最后递归地对右子树进行中序遍历。

通过这种方式,我们可以在O(n)的时间复杂度内找到二叉搜索树中第k小的元素,其中n是二叉树的节点数。

代码

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {// 创建一个ArrayList用于存储中序遍历的结果ArrayList<Integer> list = new ArrayList<>();// 定义一个方法,输入参数为二叉树的根节点和整数k,返回二叉树中第k小的元素public int kthSmallest(TreeNode root, int k) {// 先对二叉树进行中序遍历,将结果存储在list中dfs(root);// 返回list中第k-1个元素,因为数组下标从0开始,而题目要求的k是从1开始的return list.get(k - 1);}// 定义一个方法,输入参数为二叉树的节点,递归地对该节点的左子树和右子树进行中序遍历public void dfs(TreeNode root) {// 如果当前节点为空,直接返回if (root == null) {return;}// 递归地对左子树进行中序遍历dfs(root.left);// 将当前节点的值添加到list中list.add(root.val);// 递归地对右子树进行中序遍历dfs(root.right);}
}

PS:

感谢您的阅读!如果您觉得本篇文章对您有所帮助,请给予博主一个喔~

相关文章:

LeetCode--HOT100题(44)

目录 题目描述&#xff1a;230. 二叉搜索树中第K小的元素&#xff08;中等&#xff09;题目接口解题思路代码 PS: 题目描述&#xff1a;230. 二叉搜索树中第K小的元素&#xff08;中等&#xff09; 给定一个二叉搜索树的根节点 root &#xff0c;和一个整数 k &#xff0c;请你…...

大模型调试debug记录

环境&#xff1a;Linux , cuda 11.7 RuntimeError: Distributed package doesnt have NCCL built in 原因&#xff1a;pytorch安装的是cpu版本&#xff0c;需要安装支持gpu版本的 RuntimeError: Distributed package doesnt have NCCL built in - #3 by bdabykov - distrib…...

对话谷歌首席技术官肖恩,搜索引擎的里程碑,来看看搜索引擎界的大哥Algolia的“快、准、狠”突围关键

原创 | 文 BFT机器人 人物背景 Character Background Sean Mullaney是Algolia&#xff08;端到端人工智能搜索和发现平台&#xff09;的首席技术官&#xff0c;也是前 Stripe和谷歌高管&#xff0c;拥有扩展工程组织、开发人工智能驱动的搜索和发现工具以及在全球范围内发展A…...

DP读书:鲲鹏处理器 架构与编程(十二)鲲鹏软件实战案例

10min速通了解鲲鹏软件实战案例 云服务器源码移植与编译配置云服务器Porting Advisor代码移植搭建交叉编译环境x86云服务器交叉编译 OpenSSL鲲鹏云服务器上编译 OpenSSL Docker的安装与应用安装DockerDocker运行与验证Docker常用命令卸载Docker安装适配鲲鹏架构的Docker镜像 KV…...

前端 -- 基础 VSCode 工具生成骨架标签新增代码 解释详解

目录 文档类型声明标签 Lang 语言种类 字符集 文档类型声明标签 <!DOCTYPE> 文档类型声明&#xff0c;作用就是告诉浏览器 当前的页面是 使用哪种 HTML 版本 来显示的网页 HTML 版本也很多呀 &#xff0c;比如 &#xff1a; HTML5 ,HTML4&#xff0c;XHTML 等…...

爬虫逆向实战(二十三)--某准网数据

一、数据接口分析 主页地址&#xff1a;某准网 1、抓包 通过抓包可以发现数据接口是api_to/search/company_v2.json 2、判断是否有加密参数 请求参数是否加密&#xff1f; 通过查看“载荷”模块可以发现b参数和kiv参数是加密参数 请求头是否加密&#xff1f; 无响应是否加…...

ruoyi--数据权限

这篇文章我先和大家分析一下 RuoYi-Vue 脚手架中 DataScope 注解的实现原理&#xff0c;在 TienChin 项目视频中到时候还会有深入讲解。 1. 思路分析 首先我们先来捋一捋这里的权限实现的思路。 DataScope 注解处理的内容叫做数据权限&#xff0c;就是说你这个用户登录后能够…...

快速开发平台是什么?和传统开发平台相比有哪些区别?

本文可以从【快速开发平台的价值、和传统平台的区别、使用感受】三个方面来说明。 首先&#xff0c;我们要清楚快速开发平台是什么&#xff1a; 快速开发平台也称为低代码或无代码平台&#xff0c;旨在通过可视化工具、拖放式界面和预构建组件&#xff0c;使应用程序的开发过…...

Android基于JNI的Java与C++互调

java调用C++: #include <jni.h> //导出c函数格式 extern "C" JNIEXPORT //供JNI调用 JNICALL 函数名格式 Java_包名_类名_函数名(包名.替换为_) Java_com_example_getapplist_MainActivity_stringFromJNI 包名:com_example_getapplist 类名:MainActi…...

【算法与数据结构】513、LeetCode找树左下角的值

文章目录 一、题目二、解法三、完整代码 所有的LeetCode题解索引&#xff0c;可以看这篇文章——【算法和数据结构】LeetCode题解。 一、题目 二、解法 思路分析&#xff1a;这道题用层序遍历来做比较简单&#xff0c;最底层最左边节点就是层序遍历当中最底层元素容器的第一个值…...

React——组件缓存 react-activation

1、安装依赖 npm i -S react-activation 2、包裹根组件 import { AliveScope } from "react-activation"<AliveScope><App /> </AliveScope> 3、缓存组件 import { KeepAlive } from "react-activation"export default () > {co…...

EV代码签名证书是什么?

在数字世界中&#xff0c;很多软件和应用都需要进行代码签名&#xff0c;以确保其来源可靠和安全&#xff0c;EV代码签名证书恰好都能做到&#xff0c;那么EV代码签名证书是什么&#xff1f;它有什么功能特点呢&#xff1f;下面的内容可以给到答案。 EV代码签名证书是什么&…...

融媒行业落地客户旅程编排,详解数字化用户运营实战

移动互联网时代是流量红利的时代&#xff0c;企业常用低成本的方式进行获客&#xff0c;“增长黑客”的概念大范围传播。与此同时&#xff0c;机构媒体受到传播环境的影响&#xff0c;也开始启动全行业的媒体融合转型。在此背景下&#xff0c;2015 年神策数据成立&#xff0c;核…...

PDF制作成翻页电子书

在日常工作中&#xff0c;大部分人使用的都是PDF文档发送给客户&#xff0c;但是PDF文档通常是静态的&#xff0c;缺乏交互性和视觉吸引力。那你有没有想过把它转换成翻页的电子书呢&#xff1f; 小编将告诉你操作步骤&#xff0c;非常简单 1.搜索FLBOOK在线制作电子杂志平台 …...

多线程

1. 线程池 1.1 线程状态介绍 当线程被创建并启动以后&#xff0c;它既不是一启动就进入了执行状态&#xff0c;也不是一直处于执行状态。线程对象在不同的时期有不同的状态。那么Java中的线程存在哪几种状态呢&#xff1f;Java中的线程 状态被定义在了java.lang.Thread.Stat…...

BingChat与ChatGPT比较,哪个聊天机器人能让你获益更多?

人工智能领域的最新进展为普通人创造新的收入来源提供了更多机会。今年早些时候&#xff0c;微软对OpenAI进行了大量投资。此后&#xff0c;微软在Microsoft Edge浏览器中推出了自家的聊天机器人Bing Chat。 在论坛和社交媒体上&#xff0c;你可以发现这两个AI工具都吸引了很…...

Qt读写ini配置文件(QSettings)、XML

1、ini相关的 总结&#xff1a;Qt读写ini配置文件(QSettings) - 布丁Plus - 博客园 (cnblogs.com) Qt读写ini文件&#xff08;含源码注释&#xff09;_qt ini文件读写_lw向北.的博客-CSDN博客 2、XML相关的 Qt读写XML文件&#xff08;含源码注释&#xff09;_qt写xml_lw向北…...

JVM知识点(二)

1、G1垃圾收集器 -XX:MaxGCPauseMillis10&#xff0c;G1的参数&#xff0c;表示在任意1s时间内&#xff0c;停顿时间不能超过10ms&#xff1b;G1将堆切分成很多小堆区&#xff08;Region&#xff09;&#xff0c;每一个Region可以是Eden、Survivor或Old区&#xff1b;这些区在…...

代码随想录算法训练营day44 | LeetCode 518. 零钱兑换 II 377. 组合总和 Ⅳ

今晚学习了完全背包的做法&#xff0c;和01背包的差别具体来说就是一个可以重复&#xff0c;一个不可以重复。体现在数组的遍历中来说就是完全背包不能用二维数组做法&#xff08;因为二维dp数组一定不会重复&#xff0c;但是还没验证过&#xff09;&#xff0c;只能用一维dp数…...

Vue2向Vue3过度核心技术工程化开发和脚手架

目录 1 工程化开发和脚手架1.1 开发Vue的两种方式1.2.脚手架Vue CLI 2 项目目录介绍和运行流程2.1 项目目录介绍2.2 运行流程 3 组件化开发4 根组件 App.vue4.1 根组件介绍4.2 组件是由三部分构成4.3 总结 5 普通组件的注册使用-局部注册5.1 特点&#xff1a;5.2 步骤&#xff…...

uniapp 对接腾讯云IM群组成员管理(增删改查)

UniApp 实战&#xff1a;腾讯云IM群组成员管理&#xff08;增删改查&#xff09; 一、前言 在社交类App开发中&#xff0c;群组成员管理是核心功能之一。本文将基于UniApp框架&#xff0c;结合腾讯云IM SDK&#xff0c;详细讲解如何实现群组成员的增删改查全流程。 权限校验…...

label-studio的使用教程(导入本地路径)

文章目录 1. 准备环境2. 脚本启动2.1 Windows2.2 Linux 3. 安装label-studio机器学习后端3.1 pip安装(推荐)3.2 GitHub仓库安装 4. 后端配置4.1 yolo环境4.2 引入后端模型4.3 修改脚本4.4 启动后端 5. 标注工程5.1 创建工程5.2 配置图片路径5.3 配置工程类型标签5.4 配置模型5.…...

基于FPGA的PID算法学习———实现PID比例控制算法

基于FPGA的PID算法学习 前言一、PID算法分析二、PID仿真分析1. PID代码2.PI代码3.P代码4.顶层5.测试文件6.仿真波形 总结 前言 学习内容&#xff1a;参考网站&#xff1a; PID算法控制 PID即&#xff1a;Proportional&#xff08;比例&#xff09;、Integral&#xff08;积分&…...

.Net框架,除了EF还有很多很多......

文章目录 1. 引言2. Dapper2.1 概述与设计原理2.2 核心功能与代码示例基本查询多映射查询存储过程调用 2.3 性能优化原理2.4 适用场景 3. NHibernate3.1 概述与架构设计3.2 映射配置示例Fluent映射XML映射 3.3 查询示例HQL查询Criteria APILINQ提供程序 3.4 高级特性3.5 适用场…...

STM32标准库-DMA直接存储器存取

文章目录 一、DMA1.1简介1.2存储器映像1.3DMA框图1.4DMA基本结构1.5DMA请求1.6数据宽度与对齐1.7数据转运DMA1.8ADC扫描模式DMA 二、数据转运DMA2.1接线图2.2代码2.3相关API 一、DMA 1.1简介 DMA&#xff08;Direct Memory Access&#xff09;直接存储器存取 DMA可以提供外设…...

零基础在实践中学习网络安全-皮卡丘靶场(第九期-Unsafe Fileupload模块)(yakit方式)

本期内容并不是很难&#xff0c;相信大家会学的很愉快&#xff0c;当然对于有后端基础的朋友来说&#xff0c;本期内容更加容易了解&#xff0c;当然没有基础的也别担心&#xff0c;本期内容会详细解释有关内容 本期用到的软件&#xff1a;yakit&#xff08;因为经过之前好多期…...

九天毕昇深度学习平台 | 如何安装库?

pip install 库名 -i https://pypi.tuna.tsinghua.edu.cn/simple --user 举个例子&#xff1a; 报错 ModuleNotFoundError: No module named torch 那么我需要安装 torch pip install torch -i https://pypi.tuna.tsinghua.edu.cn/simple --user pip install 库名&#x…...

Neko虚拟浏览器远程协作方案:Docker+内网穿透技术部署实践

前言&#xff1a;本文将向开发者介绍一款创新性协作工具——Neko虚拟浏览器。在数字化协作场景中&#xff0c;跨地域的团队常需面对实时共享屏幕、协同编辑文档等需求。通过本指南&#xff0c;你将掌握在Ubuntu系统中使用容器化技术部署该工具的具体方案&#xff0c;并结合内网…...

Linux 下 DMA 内存映射浅析

序 系统 I/O 设备驱动程序通常调用其特定子系统的接口为 DMA 分配内存&#xff0c;但最终会调到 DMA 子系统的dma_alloc_coherent()/dma_alloc_attrs() 等接口。 关于 dma_alloc_coherent 接口详细的代码讲解、调用流程&#xff0c;可以参考这篇文章&#xff0c;我觉得写的非常…...

21-Oracle 23 ai-Automatic SQL Plan Management(SPM)

小伙伴们&#xff0c;有没有迁移数据库完毕后或是突然某一天在同一个实例上同样的SQL&#xff0c; 性能不一样了、业务反馈卡顿、业务超时等各种匪夷所思的现状。 于是SPM定位开始&#xff0c;OCM考试中SPM必考。 其他的AWR、ASH、SQLHC、SQLT、SQL profile等换作下一个话题…...