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

【二叉树】Leetcode 230. 二叉搜索树中第K小的元素【中等】

二叉搜索树中第K小的元素

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

示例1:
在这里插入图片描述
输入:root = [3,1,4,null,2], k = 1
输出:1

解题思路

二叉搜索树的中序遍历结果是有序的,因此可以通过中序遍历来找到第k个最小元素。

  • 1、进行中序遍历二叉搜索树,递归地遍历左子树、当前节点、右子树。
  • 2、使用一个全局变量count记录当前已经遍历到的节点个数。
  • 3、在每次遍历到一个节点时,count加1,如果count等于k,则返回当前节点的值。
  • 4、如果count小于k,则继续递归遍历右子树。

Java实现

public class KthSmallestBST {static class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int val) {this.val = val;}}private int count;private int result;public int kthSmallest(TreeNode root, int k) {count = 0;result = 0;inorderTraversal(root, k);return result;}private void inorderTraversal(TreeNode root, int k) {if (root == null || count >= k) {return;}// 中序遍历,先访问左子树inorderTraversal(root.left, k);// 访问当前节点count++;if (count == k) {result = root.val;return;}// 再访问右子树inorderTraversal(root.right, k);}public static void main(String[] args) {TreeNode root = new TreeNode(3);root.left = new TreeNode(1);root.right = new TreeNode(4);root.left.right = new TreeNode(2);KthSmallestBST solution = new KthSmallestBST();int k = 2;int result = solution.kthSmallest(root, k);System.out.println("The " + k + "th smallest element is: " + result);}
}

时间空间复杂度

  • 时间复杂度:O(n),其中n是二叉搜索树中的节点数,每个节点都需要访问一次。
  • 空间复杂度:O(height),递归调用栈的深度为树的高度。

相关文章:

【二叉树】Leetcode 230. 二叉搜索树中第K小的元素【中等】

二叉搜索树中第K小的元素 给定一个二叉搜索树的根节点 root ,和一个整数 k ,请你设计一个算法查找其中第 k 个最小元素(从 1 开始计数)。 示例1: 输入:root [3,1,4,null,2], k 1 输出:1 解…...

JS中常用的几种事件

在js中分为多种事件,比如点击事件,焦点事件,加载事件,鼠标事件等等... ... 点击事件 onclick点击事件,ondblclick双击事件 焦点事件 onblur元素失去焦点,onfocus元素获取焦点 加载事件 onload一个页面…...

Android WebView的使用与后退键处理

目录 前言首先,我们需要在布局文件中添加webView组件在Activity中获取webView实例,并加载网页内容 前言 webView是Android中常用的组件之一,用于展示网页内容。它可以加载HTML文件、URL链接等网页内容,并提供交互功能。在使用webV…...

【备忘录】Docker 2375远程端口安全漏洞解决

最近为了项目需要,把docker 的远程端口2375 给开放了。不出意外出意外了。没多久,网站报流量告警,第一反应就是开放2375这个端口问题导致,毫不迟疑直接切换服务器。关闭该台服务器的docker服务,并逐步清理掉挖矿进程&a…...

343. 整数拆分(力扣LeetCode)

文章目录 343. 整数拆分题目描述动态规划 343. 整数拆分 题目描述 给定一个正整数 n ,将其拆分为 k 个 正整数 的和( k > 2 ),并使这些整数的乘积最大化。 返回 你可以获得的最大乘积 。 示例 1: 输入: n 2 输出: 1 解释:…...

Spring面试题系列-3

Spring框架是由于软件开发的复杂性而创建的。Spring使用的是基本的JavaBean来完成以前只可能由EJB完成的事情。然而,Spring的用途不仅仅限于服务器端的开发。从简单性、可测试性和松耦合性角度而言,绝大部分Java应用都可以从Spring中受益。 Spring的属性…...

【比特币】比特币的奥秘、禁令的深层逻辑与风云变幻

导语: 比特币(Bitcoin),这个充满神秘色彩的数字货币,自诞生以来便成为各界瞩目的焦点。它背后所蕴含的Mining机制、禁令背后的深层逻辑以及市场的风云变幻,都让人欲罢不能。今天,我们将深入挖掘比特币的每一个角落&…...

【情感分析概述】

文章目录 一、情感极性分析概述1. 定义2. 情感极性的类别3. 应用场景 二、情感极性分析的技术方法1. 基于规则的方法a. 关键词打分b. 情感词典的使用 2. 基于机器学习的方法a. 监督学习方法b. 深度学习方法 三、Python进行情感极性分析 一、情感极性分析概述 情感极性分析&…...

【御控物联】JavaScript JSON结构转换(12):对象To数组——键值互换属性重组

文章目录 一、JSON结构转换是什么?二、核心构件之转换映射三、案例之《JSON对象 To JSON数组》四、代码实现五、在线转换工具六、技术资料 一、JSON结构转换是什么? JSON结构转换指的是将一个JSON对象或JSON数组按照一定规则进行重组、筛选、映射或转换…...

5.6 物联网RK3399项目开发实录-Android开发之U-Boot 编译及使用(wulianjishu666)

物联网入门到项目实干案例下载: https://pan.baidu.com/s/1fHRxXBqRKTPvXKFOQsP80Q?pwdh5ug --------------------------------------------------------------------------------------------------------------------------------- U-Boot 使用 前言 RK U-B…...

Python版【植物大战僵尸 +源码】

文章目录 写在前面:功能实现环境要求怎么玩个性化定义项目演示:源码分享Map地图:Menubar.py主菜单 主函数:项目开源地址 写在前面: 今天给大家推荐一个Gtihub开源项目:PythonPlantsVsZombies,翻译成中就是…...

【明道云】如何让用户可以新增但不能修改记录

【背景】 遇到一个需求场景,用户希望新增数据后锁住数据不让更改。 【分析】 在设计表单时直接将字段设置只读是不行的。字段设置只读将会直接让界面上此字段的前端组件不可编辑。包括新增时也无法填入。显然是不符合需求的。 需要既能新增,新增后又不…...

GPT-1原理-Improving Language Understanding by Generative Pre-Training

文章目录 前言提出动机模型猜想模型提出模型结构模型参数 模型预训练训练的目标训练方式训练参数预训练数据集预训练疑问点 模型微调模型输入范式模型训练微调建议微调疑问点 实验结果分析GPT-1缺陷 前言 首先想感慨一波 这是当下最流行的大模型的的开篇之作,由Op…...

web3.0入门及学习路径

Web3是指下一代互联网的演进形式,它涉及一系列技术和理念,旨在实现去中心化、开放、透明和用户主导的互联网体验。Web3的目标是赋予用户更多的控制权和数据所有权,并通过区块链、加密货币和分布式技术来实现。 一、特点 去中心化&#xff1…...

MATLAB 自定义中值滤波(54)

MATLAB 自定义中值滤波(54) 一、算法介绍二、算法实现1.原理2.代码一、算法介绍 中值滤波,是一种常见的点云平滑算法,改善原始点云的数据质量问题,MATLAB自带的工具似乎不太友好,这里提供自定义实现的点云中值滤波算法,具体效果如下所示: 中值滤波前: 中值滤波后:…...

harmonyOS的客户端存贮

什么是客户端存贮 在harmonyOS中,客户端存贮是指将数据存贮在本地设备以供应用程序使用; 注: 和feaureAblity搭配使用,content上下文的获取依赖该API如下: // 引入: import featureAbility from ohos.ability.featureAbility;// 使用: let content featureAbility.getConten…...

安科瑞智慧安全用电综合解决方案

概述 智慧用电管理云平台是智慧城市建设的延伸成果,将电力物联网技术与云平台的大数据分析功能相结合,实现用电信息的可视化管理,可帮助用户实现安全用电,节约用电,可靠用电。平台支持web,app,微…...

Web 前端性能优化之二:图像优化

1、图像优化 HTTP Archive上的数据显示,网站传输的数据中,60%的资源都是由各种图像文件组成的。 **图像资源优化的根本思想,可以归结为两个字:压缩。**无论是选取何种图像的文件格式,还是针对同一种格式压缩至更小的…...

android——枚举enum

在Kotlin中,枚举(Enum)是一种特殊的类,用于表示固定数量的常量。它允许你定义一组命名的常量值,这些值在程序中具有固定的意义。Kotlin的枚举功能强大,支持多种特性,如伴生对象、构造函数、属性…...

Day54:WEB攻防-XSS跨站Cookie盗取表单劫持网络钓鱼溯源分析项目平台框架

目录 XSS跨站-攻击利用-凭据盗取 XSS跨站-攻击利用-数据提交 XSS跨站-攻击利用-flash钓鱼 XSS跨站-攻击利用-溯源综合 知识点: 1、XSS跨站-攻击利用-凭据盗取 2、XSS跨站-攻击利用-数据提交 3、XSS跨站-攻击利用-网络钓鱼 4、XSS跨站-攻击利用-溯源综合 漏洞原理…...

浏览器访问 AWS ECS 上部署的 Docker 容器(监听 80 端口)

✅ 一、ECS 服务配置 Dockerfile 确保监听 80 端口 EXPOSE 80 CMD ["nginx", "-g", "daemon off;"]或 EXPOSE 80 CMD ["python3", "-m", "http.server", "80"]任务定义(Task Definition&…...

浅谈 React Hooks

React Hooks 是 React 16.8 引入的一组 API,用于在函数组件中使用 state 和其他 React 特性(例如生命周期方法、context 等)。Hooks 通过简洁的函数接口,解决了状态与 UI 的高度解耦,通过函数式编程范式实现更灵活 Rea…...

在软件开发中正确使用MySQL日期时间类型的深度解析

在日常软件开发场景中,时间信息的存储是底层且核心的需求。从金融交易的精确记账时间、用户操作的行为日志,到供应链系统的物流节点时间戳,时间数据的准确性直接决定业务逻辑的可靠性。MySQL作为主流关系型数据库,其日期时间类型的…...

centos 7 部署awstats 网站访问检测

一、基础环境准备(两种安装方式都要做) bash # 安装必要依赖 yum install -y httpd perl mod_perl perl-Time-HiRes perl-DateTime systemctl enable httpd # 设置 Apache 开机自启 systemctl start httpd # 启动 Apache二、安装 AWStats&#xff0…...

2025 后端自学UNIAPP【项目实战:旅游项目】6、我的收藏页面

代码框架视图 1、先添加一个获取收藏景点的列表请求 【在文件my_api.js文件中添加】 // 引入公共的请求封装 import http from ./my_http.js// 登录接口(适配服务端返回 Token) export const login async (code, avatar) > {const res await http…...

多种风格导航菜单 HTML 实现(附源码)

下面我将为您展示 6 种不同风格的导航菜单实现&#xff0c;每种都包含完整 HTML、CSS 和 JavaScript 代码。 1. 简约水平导航栏 <!DOCTYPE html> <html lang"zh-CN"> <head><meta charset"UTF-8"><meta name"viewport&qu…...

#Uniapp篇:chrome调试unapp适配

chrome调试设备----使用Android模拟机开发调试移动端页面 Chrome://inspect/#devices MuMu模拟器Edge浏览器&#xff1a;Android原生APP嵌入的H5页面元素定位 chrome://inspect/#devices uniapp单位适配 根路径下 postcss.config.js 需要装这些插件 “postcss”: “^8.5.…...

基于SpringBoot在线拍卖系统的设计和实现

摘 要 随着社会的发展&#xff0c;社会的各行各业都在利用信息化时代的优势。计算机的优势和普及使得各种信息系统的开发成为必需。 在线拍卖系统&#xff0c;主要的模块包括管理员&#xff1b;首页、个人中心、用户管理、商品类型管理、拍卖商品管理、历史竞拍管理、竞拍订单…...

【前端异常】JavaScript错误处理:分析 Uncaught (in promise) error

在前端开发中&#xff0c;JavaScript 异常是不可避免的。随着现代前端应用越来越多地使用异步操作&#xff08;如 Promise、async/await 等&#xff09;&#xff0c;开发者常常会遇到 Uncaught (in promise) error 错误。这个错误是由于未正确处理 Promise 的拒绝&#xff08;r…...

学习一下用鸿蒙​​DevEco Studio HarmonyOS5实现百度地图

在鸿蒙&#xff08;HarmonyOS5&#xff09;中集成百度地图&#xff0c;可以通过以下步骤和技术方案实现。结合鸿蒙的分布式能力和百度地图的API&#xff0c;可以构建跨设备的定位、导航和地图展示功能。 ​​1. 鸿蒙环境准备​​ ​​开发工具​​&#xff1a;下载安装 ​​De…...