当前位置: 首页 > 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…...

AI-调查研究-01-正念冥想有用吗?对健康的影响及科学指南

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

XCTF-web-easyupload

试了试php&#xff0c;php7&#xff0c;pht&#xff0c;phtml等&#xff0c;都没有用 尝试.user.ini 抓包修改将.user.ini修改为jpg图片 在上传一个123.jpg 用蚁剑连接&#xff0c;得到flag...

CVPR 2025 MIMO: 支持视觉指代和像素grounding 的医学视觉语言模型

CVPR 2025 | MIMO&#xff1a;支持视觉指代和像素对齐的医学视觉语言模型 论文信息 标题&#xff1a;MIMO: A medical vision language model with visual referring multimodal input and pixel grounding multimodal output作者&#xff1a;Yanyuan Chen, Dexuan Xu, Yu Hu…...

将对透视变换后的图像使用Otsu进行阈值化,来分离黑色和白色像素。这句话中的Otsu是什么意思?

Otsu 是一种自动阈值化方法&#xff0c;用于将图像分割为前景和背景。它通过最小化图像的类内方差或等价地最大化类间方差来选择最佳阈值。这种方法特别适用于图像的二值化处理&#xff0c;能够自动确定一个阈值&#xff0c;将图像中的像素分为黑色和白色两类。 Otsu 方法的原…...

大学生职业发展与就业创业指导教学评价

这里是引用 作为软工2203/2204班的学生&#xff0c;我们非常感谢您在《大学生职业发展与就业创业指导》课程中的悉心教导。这门课程对我们即将面临实习和就业的工科学生来说至关重要&#xff0c;而您认真负责的教学态度&#xff0c;让课程的每一部分都充满了实用价值。 尤其让我…...

如何理解 IP 数据报中的 TTL?

目录 前言理解 前言 面试灵魂一问&#xff1a;说说对 IP 数据报中 TTL 的理解&#xff1f;我们都知道&#xff0c;IP 数据报由首部和数据两部分组成&#xff0c;首部又分为两部分&#xff1a;固定部分和可变部分&#xff0c;共占 20 字节&#xff0c;而即将讨论的 TTL 就位于首…...

高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数

高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数 在软件开发中,单例模式(Singleton Pattern)是一种常见的设计模式,确保一个类仅有一个实例,并提供一个全局访问点。在多线程环境下,实现单例模式时需要注意线程安全问题,以防止多个线程同时创建实例,导致…...

C++.OpenGL (20/64)混合(Blending)

混合(Blending) 透明效果核心原理 #mermaid-svg-SWG0UzVfJms7Sm3e {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-SWG0UzVfJms7Sm3e .error-icon{fill:#552222;}#mermaid-svg-SWG0UzVfJms7Sm3e .error-text{fill…...

比较数据迁移后MySQL数据库和OceanBase数据仓库中的表

设计一个MySQL数据库和OceanBase数据仓库的表数据比较的详细程序流程,两张表是相同的结构,都有整型主键id字段,需要每次从数据库分批取得2000条数据,用于比较,比较操作的同时可以再取2000条数据,等上一次比较完成之后,开始比较,直到比较完所有的数据。比较操作需要比较…...

react-pdf(pdfjs-dist)如何兼容老浏览器(chrome 49)

之前都是使用react-pdf来渲染pdf文件&#xff0c;这次有个需求是要兼容xp环境&#xff0c;xp上chrome最高支持到49&#xff0c;虽然说iframe或者embed都可以实现预览pdf&#xff0c;但为了后续的定制化需求&#xff0c;还是需要使用js库来渲染。 chrome 49测试环境 能用的测试…...