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

LeetCode 热题 100 230. 二叉搜索树中第 K 小的元素

LeetCode 热题 100 | 230. 二叉搜索树中第 K 小的元素

大家好,今天我们来解决一道经典的二叉搜索树问题——二叉搜索树中第 K 小的元素。这道题在 LeetCode 上被标记为中等难度,要求查找二叉搜索树中的第 K 小的元素。


问题描述

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

示例 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 <= 10^4
  • 0 <= Node.val <= 10^4

解题思路

方法一:中序遍历(递归)
  1. 初步分析

    • 二叉搜索树(BST)的中序遍历可以得到一个有序的节点值序列。
    • 因此,使用中序遍历可以找到二叉搜索树中的第 K 小的元素。
  2. 步骤

    • 递归进行中序遍历,遍历到第 K 个元素时返回其值。
  3. 代码实现

class Solution:def kthSmallest(self, root: TreeNode, k: int) -> int:self.count = 0self.result = 0def travel(t):if t is None:returntravel(t.left)  # 左self.count += 1  # 中if self.count == k:self.result = t.valtravel(t.right)  # 右travel(root)return self.result
方法二:中序遍历(迭代)
  1. 初步分析

    • 如果不想使用递归,可以使用显式栈来模拟中序遍历。
    • 遍历到第 K 个元素时返回其值。
  2. 步骤

    • 使用栈模拟中序遍历,通过栈记录每次访问的节点。
  3. 代码实现

class Solution:def kthSmallest(self, root: TreeNode, k: int) -> int:stack = []current = rootwhile current or stack:while current:stack.append(current)current = current.leftcurrent = stack.pop()k -= 1if k == 0:return current.valcurrent = current.right
方法三:基于分治的优化
  1. 初步分析

    • 通过计算每个节点的左子树节点数,可以在 O(log n) 的时间复杂度内找到第 K 小的元素。
    • 如果 K 小于左子树的节点数,则在左子树中查找;如果 K 等于左子树的节点数 + 1,则当前节点即为第 K 小的元素;否则在右子树中查找。
  2. 步骤

    • 计算每个节点的左子树节点数,根据 K 的值决定在左子树还是右子树查找。
  3. 代码实现

class Solution:def kthSmallest(self, root: TreeNode, k: int) -> int:def countNodes(node):if not node:return 0return 1 + countNodes(node.left) + countNodes(node.right)left_count = countNodes(root.left)if k <= left_count:return self.kthSmallest(root.left, k)elif k > left_count + 1:return self.kthSmallest(root.right, k - left_count - 1)else:return root.val

复杂度分析

  • 时间复杂度

    • 中序遍历(递归和迭代):O(n),其中 n 是二叉搜索树的节点数。需要遍历整个树。
    • 基于分治的优化方法:O(log n) 到 O(n),最坏情况下需要遍历整个树,但在平衡树中可以在 O(log n) 内完成查找。
  • 空间复杂度

    • 中序遍历(递归):O(n),用于递归调用栈。
    • 中序遍历(迭代):O(n),用于存储栈的额外空间。
    • 基于分治的优化方法:O(h),其中 h 是树的高度,递归调用栈的深度等于树的高度。

进阶问题

如果二叉搜索树经常被修改(插入/删除操作)并且你需要频繁地查找第 K 小的值,可以考虑以下优化方法:

  1. 使用自平衡的二叉搜索树

    • 使用 AVL 树或红黑树,可以保证树的高度最小化,从而使得查找、插入和删除操作的时间复杂度为 O(log n)。
  2. 维护子树大小信息

    • 在每个节点上维护两个额外的信息:左子树中的节点数(称为“左序”)和右子树中的节点数(称为“右序”)。每次插入或删除操作后,更新这些统计信息。利用节点的左序和右序信息,可以在不完全遍历树的情况下找到第 K 小的节点。

总结

通过中序遍历的方法,我们可以高效地找到二叉搜索树中的第 K 小的元素。基于分治的优化方法可以在平衡树中进一步提高查找效率。希望这篇题解对大家有所帮助,如果有任何问题,欢迎在评论区留言讨论!

关注我,获取更多算法题解和编程技巧!

相关文章:

LeetCode 热题 100 230. 二叉搜索树中第 K 小的元素

LeetCode 热题 100 | 230. 二叉搜索树中第 K 小的元素 大家好&#xff0c;今天我们来解决一道经典的二叉搜索树问题——二叉搜索树中第 K 小的元素。这道题在 LeetCode 上被标记为中等难度&#xff0c;要求查找二叉搜索树中的第 K 小的元素。 问题描述 给定一个二叉搜索树的根…...

vscode - 笔记

1 IDE就用vscode&#xff0c;安装Remote-SSH插件通过SSH访问树莓派里的文件夹 写在开始&#xff1a;阿尔法Linux开发板学习开始 - 银色的音色 - 博客园 2 VSCode之Linux C/C开发和调试 VSCode之Linux C/C开发和调试 CMake代码编译 json配置_哔哩哔哩_bilibili 3 VS Code 凭…...

使用VSCode编辑Markdown+PlantUml

vscode :https://code.visualstudio.com/ 什么是markdown&#xff1a; Markdown 是一种轻量级标记语言&#xff0c;它允许人们使用易读易写的纯文本格式编写文档。 Markdown 编写的文档可以导出 HTML 、Word、图像、PDF、Epub 等多种格式的文档。 在vscode上安装MarkDown相关…...

关于 Golang GC 机制的一些细节:什么是根对象?GC 机制的触发时机?

文章目录 关于 Golang GC 机制的一些细节&#xff1a;什么是根对象&#xff1f;GC 机制的触发时机&#xff1f;简要回顾 Golang GC 三色标记法的工作流程什么是根对象&#xff1f;GC 的触发时机&#xff1f; 关于 Golang GC 机制的一些细节&#xff1a;什么是根对象&#xff1f…...

内存虚拟盘(RAMDisk)是什么?

内存虚拟盘&#xff08;RAMDisk&#xff09;是一种通过软件将计算机的部分物理内存&#xff08;RAM&#xff09;模拟为硬盘驱动器的技术&#xff0c;利用内存的高速读写特性显著提升数据访问效率。以下从原理、优势、实现方式及应用场景等方面详细解析&#xff1a; ​1. 技术原…...

深入浅出入侵检测系统(IDS)的工作原理与应用场景

网络安全界的“火眼金睛”&#xff1a;入侵检测系统IDS 一、IDS简介&#xff1a;网络安全界的“火眼金睛” 在计算机安全领域&#xff0c;有一个“火眼金睛”的角色&#xff0c;它能在网络世界中识破各种“妖魔鬼怪”的伪装&#xff0c;及时发出警报&#xff0c;保护我们的数…...

AISBench benchmark评测工具实操-精度评测场景-采用命令行指定模型和数据集的方式

一、环境信息 1.1.硬件设备 昇腾Atlas800 I A2:910A 01:00.0 Processing accelerators: Huawei Technologies Co., Ltd. Device d801 (rev 20) 1.2.软件信息 1.2.1模型: DeepSeek-R1-Distill-Qwen-1.5B 1.2.2.物理机系统: NAME="EulerOS" VERSION="2.0 …...

HTTP GET报文解读

考虑当浏览器发送一个HTTP GET报文时&#xff0c;通过Wireshark 俘获到下列ASCII字符串&#xff1a; GET /cs453/index.html HTTP/1.1 Host: gaia.cs.umass.edu User-Agent: Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.7.2) Gecko/20040804 Netscape/7.2 (ax) Acc…...

南审计院考研分享会 经验总结

汪学长 – 中科大 计科专硕 初试准备 数学先做真题&#xff0c;模拟题刷的越多分越高&#xff1b;408真题最重要&#xff0c;模拟题辅助&#xff1b;英语只做真题&#xff1b;政治9月份开始背 代码能力在低年级培养的重要性和路径 考研不选择机构原因 因为机构里面学习的框…...

Android多媒体——媒体解码流程分析(十四)

NuPlayer 的解码模块相对比较简单,统一使用了一个基类 NuPlayerDecoderBase 管理,该类中包含了一个 MediaCodec 的对象,实际解码工作全靠 MediaCodec。 一、解码器创建 解码器创建的入口在 NuPlayer 的 NuPlayer::instantiateDecoder() 函数调用时。NuPlayer 在执行 start(…...

学习threejs,使用Physijs物理引擎,通过控制重力,实现多米诺骨牌效果

&#x1f468;‍⚕️ 主页&#xff1a; gis分享者 &#x1f468;‍⚕️ 感谢各位大佬 点赞&#x1f44d; 收藏⭐ 留言&#x1f4dd; 加关注✅! &#x1f468;‍⚕️ 收录于专栏&#xff1a;threejs gis工程师 文章目录 一、&#x1f340;前言1.1 ☘️Physijs 物理引擎1.1.1 ☘️…...

自由学习记录(60)

Lecture 16 Ray Tracing 4_哔哩哔哩_bilibili 老师说的“高频采样”问题是什么&#xff1f; 现在考虑一个特殊情况&#xff1a; ❗ 一个像素内&#xff0c;图像信号变化很剧烈&#xff08;高频&#xff09;&#xff1a; 比如&#xff1a; 细网格纹理 马赛克背景 很高频的…...

Gartner《分布式和微服务架构中数据架构》学习心得

一、简介 随着信息技术的不断发展,软件架构也在持续演变以适应不断变化的业务需求。从传统的单体架构向分布式和微服务架构转变,给数据的管理带来了新的挑战和机遇。《Working With Data in Distributed and Microservices Architectures》研究针对在分布式和微服务架构中处…...

谷歌web第三方登录

1.在谷歌控制台创建客户端信息 https://console.cloud.google.com/auth/clients 注&#xff1a;在重定向的url中一定要是https开头的。 创建完成之后主要获取三个信息 clientID、secret、redirctUrl 2.配置pom <dependency><groupId>com.google.auth</group…...

ConfigMap 和 Secret 是否支持热更新

在 Kubernetes 中&#xff0c;ConfigMap 和 Secret 是否支持热更新取决于它们的使用方式和应用程序的行为。以下是详细分析&#xff1a; 1. ConfigMap 的热更新 场景 1&#xff1a;通过 Volume 挂载到 Pod 支持热更新&#xff1a; 如果 Pod 通过 volume 挂载 ConfigMap&#…...

时序数据库IoTDB分布式系统监控基础概述

在分布式系统环境中&#xff0c;系统性能调优与瓶颈定位一直是工程实践与架构设计中的关键挑战。面对诸如系统性能无法提升、查询延迟增加等问题&#xff0c;需要一套有效的监控体系来洞察系统的内部状态与运行情况。 可观测性概念 随着分布式架构的普及&#xff0c;可观测性…...

【乱码】前端js流式输出因为Uint8Array字节不完整导致乱码问题

【乱码】流式输出因为Uint8Array字节不完整导致乱码问题 function push() {reader.read().then(({ done, value }) > {if (done) { 问题代码 var a new Uint8Array([115,44,32,115,101,114,105,102,34,62,230]) var b new Uint8Array([156,136,60,47,115,112,97,110,62…...

PDF Base64格式字符串转换为PDF文件临时文件

需求描述&#xff1a; 在对接电子病历系统与河北CA&#xff0c;进行免密文件签章的时候&#xff0c;两者系统入参不同&#xff0c;前者是pdf文件&#xff0c;base64格式&#xff1b;后者要求File类型的PDF文件。 在业务中间层开发时&#xff0c;则需要接收EMR侧提供的base64格式…...

ClickHouse详解

ClickHouse 是一款开源的列式数据库管理系统&#xff08;DBMS&#xff09;&#xff0c;由 Yandex 开发&#xff0c;专为联机分析处理&#xff08;OLAP&#xff09;设计&#xff0c;具备高性能、低延迟、海量数据处理能力&#xff0c;广泛应用于日志分析、用户行为分析、指标监控…...

Go语言中的函数类型参数:深入理解`func()`

在Go语言中&#xff0c;函数是一等公民&#xff0c;可以作为参数传递、作为返回值&#xff0c;甚至赋值给变量。其中&#xff0c;func()作为一种特殊的函数类型&#xff0c;在Go的并发编程、回调机制和接口设计中扮演着重要角色。本文将全面解析func()的用法、原理和最佳实践。…...

deepseek梳理java高级开发工程师微服务面试题-进阶版

高级Java微服务面试题与深度解析 一、Spring Cloud核心组件深度剖析 1. Eureka服务注册发现机制 题目&#xff1a;详细分析Eureka的AP特性实现原理&#xff0c;包括服务注册、续约、剔除和自我保护机制&#xff0c;并说明与Nacos的CP模式区别。 答案&#xff1a; Eureka A…...

Math工具类全面指南

Math工具类全面指南 前言一、Math 类的基础特性1.1 类的声明与常量1.2 数据类型支持 二、基础算术运算2.1 绝对值运算2.2 取整运算2.2.1 floor()&#xff1a;向下取整2.2.2 ceil()&#xff1a;向上取整2.2.3 round()&#xff1a;四舍五入取整 2.3 最大值与最小值 三、三角函数与…...

为什么 Linux 上默认没有 host.docker.internal

在 Linux 环境中&#xff0c;host.docker.internal 是 Docker 为容器提供的一个特殊 DNS 名称&#xff0c;用于指向宿主机的 IP 地址&#xff08;类似 macOS/Windows 中的行为&#xff09;。但这个功能在 Linux 上默认不启用&#xff0c;需要手动配置才能使用。以下是详细解释和…...

HTML 颜色全解析:从命名规则到 RGBA/HSL 值,附透明度设置与场景应用指南

一、HTML 颜色系统详解 HTML 中的颜色可以通过多种方式定义&#xff0c;包括颜色名称、RGB 值、十六进制值、HSL 值等&#xff0c;同时支持透明度调整。以下是详细分类及应用场景&#xff1a; 1. 颜色名称&#xff08;预定义关键字&#xff09; HTML 预定义了 140 个标准颜色名…...

HTTP / HTTPS 协议

目录 一、前言&#xff1a; 二、Fiddler 抓包工具&#xff1a; 三、http 协议&#xff1a; 1、http 请求&#xff1a; 1.&#xff08;1&#xff09;请求行&#xff1a; 1、(2) 请求头&#xff1a; 1、(3) 请求正文: 2、http 响应&#xff1a; 2、(1) 状态码&#x…...

使用GRPO训练调度事件的语言模型!

参考&#xff1a;https://huggingface.co/blog/anakin87/qwen-scheduler-grpo 现在是2025年&#xff0c;在DeepSeek热潮之后&#xff0c;每个人都想使用GRPO训练自己的推理模型。 作为一名实践者&#xff0c;我也想这样做&#xff1a;仅使用提示和奖励来训练语言模型是一件非常…...

关于 js:9. Node.js 后端相关

一、Node 环境搭建与执行流程 Node.js 是一个基于 Chrome V8 引擎的 JavaScript 运行环境&#xff0c;它让 JS 不再局限于浏览器内&#xff0c;而是可以在服务器、终端、本地脚本中运行。 核心定位&#xff1a;让我们可以用 JS 写本地程序、脚本、爬虫、加密逻辑、hook 工具、…...

More Effective C++:改善编程与设计(上)

More Effective C&#xff1a; 目录 More Effective C&#xff1a; 条款1&#xff1a;仔细区别pointers和 references 条款2:最好使用C转型操作符 条款3:绝对不要以多态方式处理数组 条款4:非必要不要提供default constructor 条款5:对定制的“类型转换函数”保持警觉 …...

SCDN如何有效防护网站免受CC攻击?——安全加速网络的实战解析

在互联网安全威胁日益复杂化的今天&#xff0c;CC&#xff08;Challenge Collapsar&#xff09;攻击已成为网站运营者面临的主要挑战之一。这种攻击通过模拟大量合法用户请求&#xff0c;消耗服务器资源&#xff0c;导致正常用户无法访问。而**安全内容分发网络&#xff08;SCD…...

关于并发编程AQS的学习

目录 1. AQS的核心作用 2. AQS的核心结构 3. 关键方法 4. AQS的应用示例 4.1、ReentrantLock的实现 4.2、CountDownLatch的实现 5. AQS的优势 6. 对比其他同步机制 前言 AQS&#xff08;AbstractQueuedSynchronizer&#xff09; 是Java并发编程中一个核心的同步器框架…...

16S18S基础知识(1)

相关内容&#xff1a; https://blog.csdn.net/weixin_34315189/article/details/86397125?fromshareblogdetail&sharetypeblogdetail&sharerId86397125&sharereferPC&sharesource2302_80012625&sharefromfrom_link https://metagenome.blog.csdn.net/art…...

Java Spring Boot 控制器中处理用户数据详解

目录 一、获取请求参数1.1 获取查询参数1.2 获取路径参数 二、处理表单提交2.1 处理表单数据 三、处理 JSON 数据3.1 接收 JSON 数据 四、返回 JSON 数据五、处理文件上传5.1 单文件上传5.2 多文件上传 六、总结 在 Spring Boot 应用开发中&#xff0c;控制器&#xff08;Contr…...

AI产品上市前的“安全通行证“

首席数据官高鹏律师团队 如今AI 产品如雨后春笋般涌现&#xff0c;从智能音箱到自动驾驶汽车&#xff0c;从语音助手到医疗诊断软件&#xff0c;它们正全方位渗透进我们的生活。然而&#xff0c;在 AI 产品迈向市场、走进千家万户之前&#xff0c;有一系列强制性安全认证如同坚…...

sql server 2019 将单用户状态修改为多用户状态

记录两种将单用户状态修改为多用户状态&#xff0c;我曾经成功过的方法&#xff0c;供参考 第一种方法 USE master; GO -- 终止所有活动连接 DECLARE kill_connections NVARCHAR(MAX) ; SELECT kill_connections KILL CAST(session_id AS NVARCHAR(10)) ; FROM sys.dm_ex…...

[滑动窗口]越短越合法(可转化成越长越合法)

题目链接 题意 给你一个整数数组 nums 和一个整数 k &#xff0c;请你返回子数组内所有元素的乘积严格小于k 的连续子数组的数目。 首先当ans增加时 我们认为r固定 方法一、转化成越长越合法 思路 算出乘积 ≥ k \ge k ≥k的子数组数量 再用所有子数组数量减去上面算出来…...

idea中编写spark程序

### 在 IntelliJ IDEA 中配置和编写 Spark 程序 要在 IntelliJ IDEA 中高效地开发 Spark 程序&#xff0c;需要完成一系列必要的环境配置以及项目搭建工作。以下是详细的说明。 --- #### 1. 安装与配置 IntelliJ IDEA 为了确保 IDE 可以支持 Scala 开发&#xff0c;首先需要…...

机器学习入门(一)

机器学习入门&#xff08;一&#xff09; 文章目录 机器学习入门&#xff08;一&#xff09;一、机器学习分类1.1 监督学习1.2 半监督学习1.3 无监督学习1.4 强化学习 二、scikit-learn工具介绍scikit-learn安装 三、数据集3.1 sklearn玩具数据集介绍3.2 sklearn现实世界数据集…...

力扣每日一题之移动零

题目说明&#xff1a; 给定一个数组 nums&#xff0c;编写一个函数将所有 0 移动到数组的末尾&#xff0c;同时保持非零元素的相对顺序。 请注意 &#xff0c;必须在不复制数组的情况下原地对数组进行操作。 思路分析&#xff1a;我们可以考虑使用双指针来解答该题。双指针分…...

GaiaEx 盖亚:从合规出发,一家新兴交易平台的全球化路径探索

在加密货币交易平台日益激烈的竞争中&#xff0c;监管趋严、安全要求提升、用户体验优化已成为行业发展的三大核心议题。2025年初正式上线的GaiaEx 盖亚交易所&#xff0c;正是在这一市场背景下&#xff0c;以“合规 产品 生态”的多维路径&#xff0c;逐步建立起自身的发展方…...

车载网关--- 职责边界划分与功能解耦设计

我是穿拖鞋的汉子,魔都中坚持长期主义的汽车电子工程师。 老规矩,分享一段喜欢的文字,避免自己成为高知识低文化的工程师: 钝感力的“钝”,不是木讷、迟钝,而是直面困境的韧劲和耐力,是面对外界噪音的通透淡然。 生活中有两种人,一种人格外在意别人的眼光;另一种人无论…...

EasyRTC嵌入式音视频通信SDK打造带屏IPC全场景实时通信解决方案

一、方案概述​ 在智能安防与物联网快速发展的背景下&#xff0c;带屏IPC&#xff08;网络摄像机&#xff09;不仅承担着视频采集与监控的基础功能&#xff0c;还逐渐向多样化交互与智能化方向演进。EasyRTC作为一款强大的实时通信框架&#xff0c;具备低延迟、高稳定性、跨平…...

STM32入门笔记(05):内部高速8Mhz时钟最大时钟可以设置 64 Mhz?如何修改system_stm32f10x.c里面的代码?

6.2 Clocks 最大系统时钟频率 当 STM32F103 系列仅使用内部高速振荡器&#xff08;HSI&#xff0c;8 MHz&#xff09;作为时钟源&#xff0c;并通过 PLL 放大时&#xff0c;最大可达 64 MHz。([forum.mikroe.com][1], [keil.com][2]) HSI 被内部除以 2&#xff08;即 4 M…...

iOS 阅后即焚功能的实现

iOS阅后即焚功能实现步骤 一、功能设计要点 消息类型支持&#xff1a;文本、图片、视频、音频等。销毁触发条件&#xff1a; 接收方首次打开消息后启动倒计时。消息存活时间可配置&#xff08;如5秒、1分钟&#xff09;。 安全要求&#xff1a; 端到端加密&#xff08;E2EE&a…...

二叉树前中后序遍历统一迭代法详解:空标记法与栈操作的艺术

二叉树的 前序、中序、后序 遍历是算法中的经典问题。递归实现简单直观&#xff0c;而迭代法则能更好地理解栈的操作逻辑。前文中(中序&#xff0c;前序与后序&#xff09;所讲过传统的迭代法需要为每种遍历设计不同的入栈顺序&#xff0c;但 统一迭代法 通过引入 空标记节点&a…...

Spark 集群配置、启动与监控指南

Spark 集群的配置和启动需要几个关键步骤。以下是完整的操作流程&#xff0c;包含配置修改、集群启动、任务提交和常见错误排查方法。 1. 修改 Spark 配置文件 首先需要编辑 Spark 配置文件&#xff0c;设置集群参数&#xff1a; bash # 进入 Spark 配置目录 cd $SPARK_HOM…...

综述:拓扑材料的热磁性质

Adv. Funct. Mater. 2025, 2506631 https://doi.org/10.1002/adfm.202506631 近年来&#xff0c;越来越多的拓扑材料表现出优异的热磁&#xff08;TM&#xff09;性能&#xff0c;其显著的双极效应和线性能带带来的高载流子迁移率改善了这种性能。 本文综述了TM输运理论、基于…...

lanqiaoOJ 652:一步之遥 ← 扩展欧几里得定理

【题目来源】 https://www.lanqiao.cn/problems/652/learning/ 【题目背景】 本题为填空题&#xff0c;只需要算出结果后&#xff0c;在代码中使用输出语句将所填结果输出即可。 【题目描述】 从昏迷中醒来&#xff0c;小明发现自己被关在X星球的废矿车里。矿车停在平直的废弃…...

双目云台摄像机:双摄安防功能全方位

双目云台摄像机是一种具有革命性设计的云台摄像机设备&#xff0c;其核心在于其独特的双摄像头配置。以下是对这种先进安防设备的详细介绍&#xff1a; 一、核心原理 双目云台摄像机的核心原理在于利用两个摄像头从不同角度捕捉同一场景&#xff0c;通过先进的算法计算两个图…...

Linux - 基础指令

目录 linux下基本指令 ls pwd cd touch mkdir rmdir rm man cp mv cat ​more less head tail | 匿名管道 find 指令 which alias grep zip/unzi rz/sz tar 重要的⼏个热键 学习linux操作系统&#xff0c;学习指令是必不可少的 尽管有图形化的linux操作系统供学者学习&am…...

深圳无人机展览即将开始,无人机舵机为什么选择伟创动力

深圳无人机展览即将开始&#xff0c;无人机舵机为什么选择伟创动力 2025年5月23日至25日&#xff0c;伟创动力(Kpower)将携旗下多款高性能舵机及微型驱动系统方案亮相2025国际低空经济与无人系统博览会&#xff08;深圳无人机展&#xff09;&#xff0c;全面展示其在无人机、机…...