二叉搜索树的第 k 大的节点
题目描述
给定一棵二叉搜索树,请找出其中第 k 大的节点。
解题基本知识
二叉搜索树(Binary Search Tree)又名二叉查找树、二叉排序树。它是一棵空树,或者是具有下列性质的二叉树: 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值; 若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值; 它的左、右子树也分别为二叉排序树。
-
解法一: 递归
利用二叉搜索树的特性进行中序遍历。先遍历左节点,然后根节点,最后遍历右节点,得到的是一个递增序列,那么序列的倒序为递减序列。因此这道题我们可以转变为求二叉搜索树中序遍历倒序的第 k 个数。
/*** Definition for a binary tree node.* function TreeNode(val) {* this.val = val;* this.left = this.right = null;* }*/ /*** @param {TreeNode} root* @param {number} k* @return {number}*/ const kthLargest = (root, k) => {let res = null; // 初始化返回值// 因为需要倒序第 k 个,所以处理是右节点,根节点,然后左节点const dfs = (root) => {if (!root) return; // 如果当前节点为 null,本轮处理结束dfs(root.right); // 开始处理右节点if (k === 0) return; // k 值 为 0,代表已经处理的节点超过目标节点,本轮处理结束if (--k === 0) {// 当 k 值 减 1 为 0,表示已经到了我们想要的 k 大 节点,保存当前值res = root.val;}dfs(root.left); // 处理左节点};dfs(root); // 从初始化节点开始处理return res; };
- 复杂度分析:
- 时间复杂度 O(N):无论 k 的值大小,递归深度都为 N,占用 O(N) 时间。
- 空间复杂度 O(N):无论 k 的值大小,递归深度都为 N,占用 O(N) 空间。
- 复杂度分析:
-
解法二: 迭代
思路还是二叉树的中序遍历,利用栈的方式进行遍历。
/*** Definition for a binary tree node.* function TreeNode(val) {* this.val = val;* this.left = this.right = null;* }*/ /*** @param {TreeNode} root* @param {number} k* @return {number}*/ var kthLargest = function (root, k) {if (!root) return 0;// 声明储存栈const stack = [];// 判断当前栈否有节点和当前遍历节点位置while (stack.length || root) {while (root) {// 往栈里添加当前节点,同时切换为右节点处理stack.push(root);root = root.right;}// 取出当前栈顶元素,根据添加的顺序,当前元素是栈内最大的const cur = stack.pop();k--;if (k === 0) return cur.val;// 切换为左节点处理root = cur.left;}return 0; };
- 复杂度分析:
- 时间复杂度 O(N):需要遍历整棵树一次,复杂度为 O(N)
- 空间复杂度 O(N):需要额外空间栈进行储存树,复杂度为 O(N)
- 复杂度分析:
相关文章:

二叉搜索树的第 k 大的节点
题目描述 给定一棵二叉搜索树,请找出其中第 k 大的节点。 解题基本知识 二叉搜索树(Binary Search Tree)又名二叉查找树、二叉排序树。它是一棵空树,或者是具有下列性质的二叉树: 若它的左子树不空,则左子…...
利用langchain 做大模型 Few-shot Learning 提示,包括固定和向量相似的动态样本筛选
文章目录 few-shotFixed Examples 固定样本Dynamic few-shot prompting 动态样本提示辅助参考资料 few-shot 相比大模型微调,在有些情况下,我们更想使用 Few-shot Learning 通过给模型喂相关样本示例,让模型能够提升相应任务的能力。 固定样…...

基于python的百度迁徙迁入、迁出数据分析(五)
终于在第五篇文章我们进入了这个系列的正题:数据分析 这里我选择上海2024年5月1日——5月5日的迁入、迁出数据作为分析的基础,首先选择节假日的数据作为分析的原因呢,主要是节假日人们出行目的比较单一(出游、探亲)&a…...
SpringBoot 如何处理跨域请求
SpringBoot 处理跨域请求,通常是通过配置全局的 CORS(跨源资源共享)策略来实现的。CORS 是一种机制,它使用额外的 HTTP 头部来告诉浏览器,让运行在一个 origin (domain) 上的 web 应用被准许访问来自不同源服务器上的指…...

大数据技术基础编程、实验和案例----大数据课程综合实验案例
一、实验目的 (1)熟悉Linux系统、MySQL、Hadoop、HBase、Hive、Sqoop、R、Eclipse等系统和软件的安装和使用; (2)了解大数据处理的基本流程; (3)熟悉数据预处理方法; (4)熟悉在不同类型数据库之…...

微信小程序-获取手机号:HttpClientErrorException: 412 Precondition Failed: [no body]
问题: 412 异常就是你的请求参数获取请求头与服务器的不符,缺少请求体! 我的问题: 我这里获取微信手机号的时候突然给我报错142,但是代码用的是原来的代码,换了一个框架就噶了! 排查问题&am…...

大数据核心概念与技术架构简介
大数据基本概念 大数据是指无法在一定时间范围内用常规软件工具进行捕捉、管理和处理的数据集合,是具有更强的决策力、洞察发现力和流程优化能力的海量、高增长率和多样化的信息资产。 大数据特征: 数据量大:一般以P(1000个TB&a…...
快排 谁在中间
原题 Whos in the Middle FJ is surveying his herd to find the most average cow. He wants to know how much milk this median cow gives: half of the cows give as much or more than the median; half give as much or less. FJ正在调查他的牛群,以找到最…...
ORA-00911: invalid character
场景: 调用接口查询oracle的数据库数据时报错ORA-00911: invalid character,但是sql语句没有问题放在navicat控制台中运行也没有问题,但是代码中跑就会报无效字符集 分析: 代码中Oracle的语法解析器比较严格,比如句…...

Pytorch实现线性回归Linear Regression
借助 PyTorch 实现深度神经网络 - 线性回归 - 第 2 周 | Coursera 线性回归预测 用PyTorch实现线性回归模块 创建自定义模块(内含一个线性回归) 训练线性回归模型 对于线性回归,特定类型的噪声是高斯噪声 平均损失均方误差函数:…...

十八次(虚拟主机与vue项目、samba磁盘映射、nfs共享)
1、虚拟主机搭建环境准备 将原有的nginx.conf文件备份 [rootserver ~]# cp /usr/local/nginx/conf/nginx.conf /usr/local/nginx/conf/nginx.conf.bak[rootserver ~]# grep -Ev "#|^$" /usr/local/nginx/conf/nginx.conf[rootserver ~]# grep -Ev "#|^$"…...

P1340 兽径管理 题解|最小生成树
题目大意 洛谷中链接 推荐文章:并查集入门 原文 约翰农场的牛群希望能够在 N N N 个草地之间任意移动。草地的编号由 1 1 1 到 N N N。草地之间有树林隔开。牛群希望能够选择草地间的路径,使牛群能够从任一 片草地移动到任一片其它草地。 牛群可在…...
Python,Maskrcnn训练,cannot import name ‘saving‘ from ‘keras.engine‘ ,等问题集合
Python版本3.9,tensorflow2.11.0,keras2.11.0 问题一、module keras.engine has no attribute Layer Traceback (most recent call last):File "C:\Users\Administrator\Desktop\20240801\代码\test.py", line 16, in <module>from mrc…...

Linux常用工具
文章目录 tar打包命令详解unzip命令:解压zip文件vim操作详解netstat详解df命令详解ps命令详解find命令详解 tar打包命令详解 tar命令做打包操作 当 tar 命令用于打包操作时,该命令的基本格式为: tar [选项] 源文件或目录此命令常用的选项及…...
AI未来的发展如何
AI(人工智能)的发展前景非常广阔,随着技术的不断进步和应用场景的不断拓展,AI将在多个领域发挥重要作用。以下是对AI发展前景的详细分析: 一、技术突破与创新 生成式AI的兴起:以ChatGPT为代表的生成式AI技…...

若依替换首页上的logo
...
sed的使用示例
场景:使用sed将多个空格变成单空格,再使用cut来切分得到需要的结果 得到后面这个文件名: ls ./ drwxr-x— 2 root root 6 Jul 18 9:00 7b40f1412d83c1524af7977593607f15 drwxr-x— 2 root root 6 Jul 18 14:00 50af29cef2c65a9d28905a3ce831bcb7 drwxr-x— 2 root root 6 Jul…...
学历不是障碍:大专生如何成功进入软件测试行业
摘要: 在当今技术驱动的职场环境中,软件测试已成为一个关键的职业领域。尽管许多人认为高学历是进入这一行业的先决条件,但实际上,大专学历的学生同样有机会在软件测试领域取得成功。本文将探讨大专生如何通过技能提升、实践经验和…...

文件解析漏洞—IIS解析漏洞—IIS6.X
目录 方式 1:目录解析 方式 2:畸形文件解析 方式 3:PUT 上传漏洞(123.asp;.jpg 解析成 asp) 环境:Windows server 2003 添加 IIS 管理工具——打开 IIS——添加网站 创建完成之后,右击创建的…...
Sqlmap中文使用手册 - Brute force模块参数使用
目录 1. Brute force模块的帮助文档2. 各个参数的介绍2.1 --common-tables2.2 --common-columns2.3 --common-files 1. Brute force模块的帮助文档 Brute force:These options can be used to run brute force checks--common-tables Check existence of common tables--c…...

springboot 百货中心供应链管理系统小程序
一、前言 随着我国经济迅速发展,人们对手机的需求越来越大,各种手机软件也都在被广泛应用,但是对于手机进行数据信息管理,对于手机的各种软件也是备受用户的喜爱,百货中心供应链管理系统被用户普遍使用,为方…...
从零实现富文本编辑器#5-编辑器选区模型的状态结构表达
先前我们总结了浏览器选区模型的交互策略,并且实现了基本的选区操作,还调研了自绘选区的实现。那么相对的,我们还需要设计编辑器的选区表达,也可以称为模型选区。编辑器中应用变更时的操作范围,就是以模型选区为基准来…...

关于iview组件中使用 table , 绑定序号分页后序号从1开始的解决方案
问题描述:iview使用table 中type: "index",分页之后 ,索引还是从1开始,试过绑定后台返回数据的id, 这种方法可行,就是后台返回数据的每个页面id都不完全是按照从1开始的升序,因此百度了下,找到了…...

关键领域软件测试的突围之路:如何破解安全与效率的平衡难题
在数字化浪潮席卷全球的今天,软件系统已成为国家关键领域的核心战斗力。不同于普通商业软件,这些承载着国家安全使命的软件系统面临着前所未有的质量挑战——如何在确保绝对安全的前提下,实现高效测试与快速迭代?这一命题正考验着…...

SAP学习笔记 - 开发26 - 前端Fiori开发 OData V2 和 V4 的差异 (Deepseek整理)
上一章用到了V2 的概念,其实 Fiori当中还有 V4,咱们这一章来总结一下 V2 和 V4。 SAP学习笔记 - 开发25 - 前端Fiori开发 Remote OData Service(使用远端Odata服务),代理中间件(ui5-middleware-simpleproxy)-CSDN博客…...
关于uniapp展示PDF的解决方案
在 UniApp 的 H5 环境中使用 pdf-vue3 组件可以实现完整的 PDF 预览功能。以下是详细实现步骤和注意事项: 一、安装依赖 安装 pdf-vue3 和 PDF.js 核心库: npm install pdf-vue3 pdfjs-dist二、基本使用示例 <template><view class"con…...

【Linux】自动化构建-Make/Makefile
前言 上文我们讲到了Linux中的编译器gcc/g 【Linux】编译器gcc/g及其库的详细介绍-CSDN博客 本来我们将一个对于编译来说很重要的工具:make/makfile 1.背景 在一个工程中源文件不计其数,其按类型、功能、模块分别放在若干个目录中,mak…...
Spring Security 认证流程——补充
一、认证流程概述 Spring Security 的认证流程基于 过滤器链(Filter Chain),核心组件包括 UsernamePasswordAuthenticationFilter、AuthenticationManager、UserDetailsService 等。整个流程可分为以下步骤: 用户提交登录请求拦…...

DBLP数据库是什么?
DBLP(Digital Bibliography & Library Project)Computer Science Bibliography是全球著名的计算机科学出版物的开放书目数据库。DBLP所收录的期刊和会议论文质量较高,数据库文献更新速度很快,很好地反映了国际计算机科学学术研…...
Python实现简单音频数据压缩与解压算法
Python实现简单音频数据压缩与解压算法 引言 在音频数据处理中,压缩算法是降低存储成本和传输效率的关键技术。Python作为一门灵活且功能强大的编程语言,提供了丰富的库和工具来实现音频数据的压缩与解压。本文将通过一个简单的音频数据压缩与解压算法…...