leetcode hot100【LeetCode 230. 二叉搜索树中第K小的元素】java实现
LeetCode 230. 二叉搜索树中第K小的元素
题目描述
给定一个二叉搜索树的根节点 root,和一个整数 k,请你找出其中第 k 小的节点。
注意:
- 题目保证
k的有效性。
示例:
给定二叉搜索树:
5/ \3 7/ \ \
2 4 6
和 k = 2,返回值应该是 3(按升序排列,第二个最小的节点是 3)。
Java 实现代码
/*** 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) {// 使用一个列表来存储中序遍历的结果List<Integer> list = new ArrayList<>();inorderTraversal(root, list);// 返回第k小的元素return list.get(k - 1);}private void inorderTraversal(TreeNode node, List<Integer> list) {if (node == null)return;// 遍历左子树inorderTraversal(node.left, list);// 访问当前节点list.add(node.val);// 遍历右子树inorderTraversal(node.right, list);}
}
解题思路
由于二叉搜索树的性质,中序遍历的结果就是升序的。因此,我们可以通过中序遍历来获取所有节点的值,并将它们存储在一个列表中。然后,我们可以直接通过索引来获取第
k小的元素。
复杂度分析
- 时间复杂度:O(N),其中 N 是树中节点的数量。因为中序遍历需要访问每一个节点。
- 空间复杂度:O(N),最坏情况下,我们需要存储所有的节点值。在最坏的情况下,树可能是一条链,此时中序遍历的结果就是所有的节点。
这个方法简单且有效,但需要注意,如果树非常大,可能会消耗较多的内存。对于更优的空间复杂度,可以考虑使用迭代的方式进行中序遍历,这样可以将空间复杂度降低到 O(H),其中 H 是树的高度。
相关文章:
leetcode hot100【LeetCode 230. 二叉搜索树中第K小的元素】java实现
LeetCode 230. 二叉搜索树中第K小的元素 题目描述 给定一个二叉搜索树的根节点 root,和一个整数 k,请你找出其中第 k 小的节点。 注意: 题目保证 k 的有效性。 示例: 给定二叉搜索树: 5/ \3 7/ \ \ 2 4 …...
从0开始深度学习(23)——图像卷积
上节了解了卷积层的原理,本节以图像为例,介绍一下它的实际应用 1 互相关运算 严格来说,卷积层是个错误的叫法,因为它所表达的运算其实是互相关运算(cross-correlation)。 首先,我们暂时忽略通…...
编程小白如何成为大神
成为编程大神的过程需要时间、耐心和实践。以下是一些适合大学新生的入门攻略: 1. 确定学习目标 选择语言:选择一门编程语言作为起点,如 Python、Java 或 JavaScript。Python 是初学者的热门选择,因为其语法简洁易懂。设定目标&…...
JetCache启动循环依赖分析
问题呈现 项目性能优化,需要将本地内存(JVM内存)替换为本地Redis(同一个Pod中的Container),降低JVM内存和GC的压力,同时引入了JetCache简化和统一使用(对JetCache也做了扩展&#x…...
【科研绘图】3DMAX管状图表生成插件TubeChart使用方法
3DMAX管状图表生成插件TubeChart,一款用于制作3D管状图表的工具。可以自定义切片的数量以及随机或指定切片颜色。 【版本要求】 3dMax 2008及更高版本 【安装方法】 TubeChart插件无需安装,使用时直接拖动插件脚本文件到3dMax视口中打开即可࿰…...
基于SSM土家风景文化管理系统的设计
管理员账户功能包括:系统首页,个人中心,用户管理,景点分类管理,热门景点管理,门票订单管理,旅游线路管理,系统管理 前提账号功能包括:系统首页,个人中心&…...
C++超强图片预览器
下载 文件打开关联 关键代码 uint32_t getSrcPx3(const cv::Mat& srcImg, int srcX, int srcY, int mainX, int mainY) const {cv::Vec3b srcPx = srcImg.at<cv::Vec3b>(srcY, srcX);intUnion ret = 255;if (curPar.zoomCur < curPar.ZOOM_BASE && src…...
网络搜索引擎Shodan(2)
声明:学习视频来自b站up主 泷羽sec,如涉及侵权马上删除文章 声明:本文主要用作技术分享,所有内容仅供参考。任何使用或依赖于本文信息所造成的法律后果均与本人无关。请读者自行判断风险,并遵循相关法律法规。 感谢泷…...
【Tableau】
Tableau 是一款强大且广泛使用的数据可视化和商业智能(BI)工具,用于帮助用户分析、探索和呈现数据。它通过直观的拖放界面,允许用户轻松创建动态仪表板和报告,而无需编写代码。Tableau 可处理多种数据源,如…...
分类与有序回归
分类问题 分类问题,例如分类猫、狗、猪时,使用数字进行表示为1,2,3。而1、2、3之间有大小,分类算法为了平衡标签之间的差异,使得损失公平,会使用one-hot编码。例如,分别使用&#x…...
Mac如何实现高效且干净的卸载应用程序
使用Mac卸载应用程序,你还在使用废纸篓这个办法吗,看不见卸载了什么,看不见清理了多少,真的不会有残留吗 XApp Mac上的卸载专家,强大的垃圾逻辑检测,垃圾扫描更全面,卸载更干净 使用简单&#…...
LaTex中的常用空格命令
【LaTex中的常用空格命令】 在 LaTeX 中,有几个常用的空格指令: ● \,:一个小空格,通常用于在数学公式中插入较小的间距。● \quad:一个等宽空格,相当于当前字体尺寸下的字符宽度。 ● \qquad:两…...
k8s 1.28.2 集群部署 Thanos 对接 MinIO 实现 Prometheus 数据长期存储
文章目录 [toc]什么是 ThanosThanos 的主要功能Thanos 的架构组件Thanos 部署架构SidecarReceive架构选择 开始部署部署架构创建 namespacenode-exporter 部署kube-state-metrics 部署Prometheus Thanos-Sidecar 部署固定节点创建 label生成 secretMinIO 配置etcd 证书 启动 P…...
域渗透AD渗透攻击利用 python脚本攻击之IPC连接 以及 python生成exe可执行程序讲解方式方法
Python脚本批量检测ipc连接 import os, timeips [192.168.1.121,192.168.1.8 ] users {administrator,hack,hack1,test, } passs {123qq.com,456qq.com,Admin12345 } for ip in ips:for user in users:for mima in passs:exec1 "net use \\" "\\" i…...
行为设计模式 -命令模式- JAVA
命令模式 一.简介二. 案例2.1 接收者(Receiver)2.2 命令接口实现对象(ConcreteCommand)2.3 调用者( invoker)2.4 获取Receiver对象2. 5 装配者客户端测试 三. 结论3.1 要点3.2 示例 前言 本设计模式专栏写了…...
使用redis实现发布订阅功能及问题
如何使用redis实现发布订阅及遇到的问题 使用背景: 服务A通过接口操作服务B,实现相应逻辑。生产环境上,服务A有两个pod,服务B有3个pod 通过接口调用时,请求只能打到服务B的一个pod上,而我们想要的是服务B的…...
Debug日程工作经验总结日程常用
数据库 db连接命令 kubectl exec -it -n de dbs-53-cdf57d8dd-l4l29 sh su - postgres psql psql -h 10.115.19.118 -p 12080 -U postgres -d clouddb SET search_path TO “h.com”; select * from ems_ice limit 1; 也可以不切换schema,直接sql查询 select * f…...
Apache Paimon主键表的一些最佳实践
今天我们说说Paimon主键表的一些使用上的注意事项。 一、主键表 主键表是Paimon的一种表类型。用户可以插入、更新或删除表中的记录。 说的直白点就是,允许你设置唯一主键,然后覆盖更新。 Bucket选择 无论分区表还是未分区表,Bucket都是最小的…...
React面试常见题目(基础-进阶)
React面试常见题目及详细回答讲解 基础题目(20个) 什么是React? 回答:React是一个用于构建用户界面的JavaScript库,它允许你将UI拆分成可复用的组件。React起源于Facebook的内部项目,用于构建高性能的Web应…...
AI赋能:开启你的副业创业之路
随着人工智能(AI)技术的迅猛发展,越来越多的人开始探索与之相关的副业机会。AI不仅深刻改变了我们的工作和生活方式,还为愿意学习和运用这项技术的人们打开了丰富的创业和增收之门。今天,我们就来盘点几条与AI相关的副…...
React Native 开发环境搭建(全平台详解)
React Native 开发环境搭建(全平台详解) 在开始使用 React Native 开发移动应用之前,正确设置开发环境是至关重要的一步。本文将为你提供一份全面的指南,涵盖 macOS 和 Windows 平台的配置步骤,如何在 Android 和 iOS…...
Python爬虫实战:研究feedparser库相关技术
1. 引言 1.1 研究背景与意义 在当今信息爆炸的时代,互联网上存在着海量的信息资源。RSS(Really Simple Syndication)作为一种标准化的信息聚合技术,被广泛用于网站内容的发布和订阅。通过 RSS,用户可以方便地获取网站更新的内容,而无需频繁访问各个网站。 然而,互联网…...
Python实现prophet 理论及参数优化
文章目录 Prophet理论及模型参数介绍Python代码完整实现prophet 添加外部数据进行模型优化 之前初步学习prophet的时候,写过一篇简单实现,后期随着对该模型的深入研究,本次记录涉及到prophet 的公式以及参数调优,从公式可以更直观…...
postgresql|数据库|只读用户的创建和删除(备忘)
CREATE USER read_only WITH PASSWORD 密码 -- 连接到xxx数据库 \c xxx -- 授予对xxx数据库的只读权限 GRANT CONNECT ON DATABASE xxx TO read_only; GRANT USAGE ON SCHEMA public TO read_only; GRANT SELECT ON ALL TABLES IN SCHEMA public TO read_only; GRANT EXECUTE O…...
多模态大语言模型arxiv论文略读(108)
CROME: Cross-Modal Adapters for Efficient Multimodal LLM ➡️ 论文标题:CROME: Cross-Modal Adapters for Efficient Multimodal LLM ➡️ 论文作者:Sayna Ebrahimi, Sercan O. Arik, Tejas Nama, Tomas Pfister ➡️ 研究机构: Google Cloud AI Re…...
selenium学习实战【Python爬虫】
selenium学习实战【Python爬虫】 文章目录 selenium学习实战【Python爬虫】一、声明二、学习目标三、安装依赖3.1 安装selenium库3.2 安装浏览器驱动3.2.1 查看Edge版本3.2.2 驱动安装 四、代码讲解4.1 配置浏览器4.2 加载更多4.3 寻找内容4.4 完整代码 五、报告文件爬取5.1 提…...
Web 架构之 CDN 加速原理与落地实践
文章目录 一、思维导图二、正文内容(一)CDN 基础概念1. 定义2. 组成部分 (二)CDN 加速原理1. 请求路由2. 内容缓存3. 内容更新 (三)CDN 落地实践1. 选择 CDN 服务商2. 配置 CDN3. 集成到 Web 架构 …...
laravel8+vue3.0+element-plus搭建方法
创建 laravel8 项目 composer create-project --prefer-dist laravel/laravel laravel8 8.* 安装 laravel/ui composer require laravel/ui 修改 package.json 文件 "devDependencies": {"vue/compiler-sfc": "^3.0.7","axios": …...
MySQL账号权限管理指南:安全创建账户与精细授权技巧
在MySQL数据库管理中,合理创建用户账号并分配精确权限是保障数据安全的核心环节。直接使用root账号进行所有操作不仅危险且难以审计操作行为。今天我们来全面解析MySQL账号创建与权限分配的专业方法。 一、为何需要创建独立账号? 最小权限原则…...
Python ROS2【机器人中间件框架】 简介
销量过万TEEIS德国护膝夏天用薄款 优惠券冠生园 百花蜂蜜428g 挤压瓶纯蜂蜜巨奇严选 鞋子除臭剂360ml 多芬身体磨砂膏280g健70%-75%酒精消毒棉片湿巾1418cm 80片/袋3袋大包清洁食品用消毒 优惠券AIMORNY52朵红玫瑰永生香皂花同城配送非鲜花七夕情人节生日礼物送女友 热卖妙洁棉…...
