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

挑战杯推荐项目

“人工智能”创意赛 - 智能艺术创作助手&#xff1a;借助大模型技术&#xff0c;开发能根据用户输入的主题、风格等要求&#xff0c;生成绘画、音乐、文学作品等多种形式艺术创作灵感或初稿的应用&#xff0c;帮助艺术家和创意爱好者激发创意、提高创作效率。 ​ - 个性化梦境…...

谷歌浏览器插件

项目中有时候会用到插件 sync-cookie-extension1.0.0&#xff1a;开发环境同步测试 cookie 至 localhost&#xff0c;便于本地请求服务携带 cookie 参考地址&#xff1a;https://juejin.cn/post/7139354571712757767 里面有源码下载下来&#xff0c;加在到扩展即可使用FeHelp…...

Ubuntu系统下交叉编译openssl

一、参考资料 OpenSSL&&libcurl库的交叉编译 - hesetone - 博客园 二、准备工作 1. 编译环境 宿主机&#xff1a;Ubuntu 20.04.6 LTSHost&#xff1a;ARM32位交叉编译器&#xff1a;arm-linux-gnueabihf-gcc-11.1.0 2. 设置交叉编译工具链 在交叉编译之前&#x…...

智慧工地云平台源码,基于微服务架构+Java+Spring Cloud +UniApp +MySql

智慧工地管理云平台系统&#xff0c;智慧工地全套源码&#xff0c;java版智慧工地源码&#xff0c;支持PC端、大屏端、移动端。 智慧工地聚焦建筑行业的市场需求&#xff0c;提供“平台网络终端”的整体解决方案&#xff0c;提供劳务管理、视频管理、智能监测、绿色施工、安全管…...

前端倒计时误差!

提示:记录工作中遇到的需求及解决办法 文章目录 前言一、误差从何而来?二、五大解决方案1. 动态校准法(基础版)2. Web Worker 计时3. 服务器时间同步4. Performance API 高精度计时5. 页面可见性API优化三、生产环境最佳实践四、终极解决方案架构前言 前几天听说公司某个项…...

SCAU期末笔记 - 数据分析与数据挖掘题库解析

这门怎么题库答案不全啊日 来简单学一下子来 一、选择题&#xff08;可多选&#xff09; 将原始数据进行集成、变换、维度规约、数值规约是在以下哪个步骤的任务?(C) A. 频繁模式挖掘 B.分类和预测 C.数据预处理 D.数据流挖掘 A. 频繁模式挖掘&#xff1a;专注于发现数据中…...

智能在线客服平台:数字化时代企业连接用户的 AI 中枢

随着互联网技术的飞速发展&#xff0c;消费者期望能够随时随地与企业进行交流。在线客服平台作为连接企业与客户的重要桥梁&#xff0c;不仅优化了客户体验&#xff0c;还提升了企业的服务效率和市场竞争力。本文将探讨在线客服平台的重要性、技术进展、实际应用&#xff0c;并…...

Module Federation 和 Native Federation 的比较

前言 Module Federation 是 Webpack 5 引入的微前端架构方案&#xff0c;允许不同独立构建的应用在运行时动态共享模块。 Native Federation 是 Angular 官方基于 Module Federation 理念实现的专为 Angular 优化的微前端方案。 概念解析 Module Federation (模块联邦) Modul…...

JDK 17 新特性

#JDK 17 新特性 /**************** 文本块 *****************/ python/scala中早就支持&#xff0c;不稀奇 String json “”" { “name”: “Java”, “version”: 17 } “”"; /**************** Switch 语句 -> 表达式 *****************/ 挺好的&#xff…...

ios苹果系统,js 滑动屏幕、锚定无效

现象&#xff1a;window.addEventListener监听touch无效&#xff0c;划不动屏幕&#xff0c;但是代码逻辑都有执行到。 scrollIntoView也无效。 原因&#xff1a;这是因为 iOS 的触摸事件处理机制和 touch-action: none 的设置有关。ios有太多得交互动作&#xff0c;从而会影响…...