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

二叉搜索树的第 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实现线性回归模块 创建自定义模块(内含一个线性回归) 训练线性回归模型 对于线性回归,特定类型的噪声是高斯噪声 平均损失均方误差函数&#xff1a…...

十八次(虚拟主机与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&#xff0c;tensorflow2.11.0&#xff0c;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命令&#xff1a;解压zip文件vim操作详解netstat详解df命令详解ps命令详解find命令详解 tar打包命令详解 tar命令做打包操作 当 tar 命令用于打包操作时&#xff0c;该命令的基本格式为&#xff1a; tar [选项] 源文件或目录此命令常用的选项及…...

AI未来的发展如何

AI&#xff08;人工智能&#xff09;的发展前景非常广阔&#xff0c;随着技术的不断进步和应用场景的不断拓展&#xff0c;AI将在多个领域发挥重要作用。以下是对AI发展前景的详细分析&#xff1a; 一、技术突破与创新 生成式AI的兴起&#xff1a;以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…...

学历不是障碍:大专生如何成功进入软件测试行业

摘要&#xff1a; 在当今技术驱动的职场环境中&#xff0c;软件测试已成为一个关键的职业领域。尽管许多人认为高学历是进入这一行业的先决条件&#xff0c;但实际上&#xff0c;大专学历的学生同样有机会在软件测试领域取得成功。本文将探讨大专生如何通过技能提升、实践经验和…...

文件解析漏洞—IIS解析漏洞—IIS6.X

目录 方式 1&#xff1a;目录解析 方式 2&#xff1a;畸形文件解析 方式 3&#xff1a;PUT 上传漏洞&#xff08;123.asp;.jpg 解析成 asp&#xff09; 环境&#xff1a;Windows server 2003 添加 IIS 管理工具——打开 IIS——添加网站 创建完成之后&#xff0c;右击创建的…...

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…...

KubeSphere 容器平台高可用:环境搭建与可视化操作指南

Linux_k8s篇 欢迎来到Linux的世界&#xff0c;看笔记好好学多敲多打&#xff0c;每个人都是大神&#xff01; 题目&#xff1a;KubeSphere 容器平台高可用&#xff1a;环境搭建与可视化操作指南 版本号: 1.0,0 作者: 老王要学习 日期: 2025.06.05 适用环境: Ubuntu22 文档说…...

2025年能源电力系统与流体力学国际会议 (EPSFD 2025)

2025年能源电力系统与流体力学国际会议&#xff08;EPSFD 2025&#xff09;将于本年度在美丽的杭州盛大召开。作为全球能源、电力系统以及流体力学领域的顶级盛会&#xff0c;EPSFD 2025旨在为来自世界各地的科学家、工程师和研究人员提供一个展示最新研究成果、分享实践经验及…...

基于ASP.NET+ SQL Server实现(Web)医院信息管理系统

医院信息管理系统 1. 课程设计内容 在 visual studio 2017 平台上&#xff0c;开发一个“医院信息管理系统”Web 程序。 2. 课程设计目的 综合运用 c#.net 知识&#xff0c;在 vs 2017 平台上&#xff0c;进行 ASP.NET 应用程序和简易网站的开发&#xff1b;初步熟悉开发一…...

遍历 Map 类型集合的方法汇总

1 方法一 先用方法 keySet() 获取集合中的所有键。再通过 gey(key) 方法用对应键获取值 import java.util.HashMap; import java.util.Set;public class Test {public static void main(String[] args) {HashMap hashMap new HashMap();hashMap.put("语文",99);has…...

【Linux】C语言执行shell指令

在C语言中执行Shell指令 在C语言中&#xff0c;有几种方法可以执行Shell指令&#xff1a; 1. 使用system()函数 这是最简单的方法&#xff0c;包含在stdlib.h头文件中&#xff1a; #include <stdlib.h>int main() {system("ls -l"); // 执行ls -l命令retu…...

质量体系的重要

质量体系是为确保产品、服务或过程质量满足规定要求&#xff0c;由相互关联的要素构成的有机整体。其核心内容可归纳为以下五个方面&#xff1a; &#x1f3db;️ 一、组织架构与职责 质量体系明确组织内各部门、岗位的职责与权限&#xff0c;形成层级清晰的管理网络&#xf…...

2021-03-15 iview一些问题

1.iview 在使用tree组件时&#xff0c;发现没有set类的方法&#xff0c;只有get&#xff0c;那么要改变tree值&#xff0c;只能遍历treeData&#xff0c;递归修改treeData的checked&#xff0c;发现无法更改&#xff0c;原因在于check模式下&#xff0c;子元素的勾选状态跟父节…...

ElasticSearch搜索引擎之倒排索引及其底层算法

文章目录 一、搜索引擎1、什么是搜索引擎?2、搜索引擎的分类3、常用的搜索引擎4、搜索引擎的特点二、倒排索引1、简介2、为什么倒排索引不用B+树1.创建时间长,文件大。2.其次,树深,IO次数可怕。3.索引可能会失效。4.精准度差。三. 倒排索引四、算法1、Term Index的算法2、 …...

安宝特方案丨船舶智造的“AR+AI+作业标准化管理解决方案”(装配)

船舶制造装配管理现状&#xff1a;装配工作依赖人工经验&#xff0c;装配工人凭借长期实践积累的操作技巧完成零部件组装。企业通常制定了装配作业指导书&#xff0c;但在实际执行中&#xff0c;工人对指导书的理解和遵循程度参差不齐。 船舶装配过程中的挑战与需求 挑战 (1…...

AGain DB和倍数增益的关系

我在设置一款索尼CMOS芯片时&#xff0c;Again增益0db变化为6DB&#xff0c;画面的变化只有2倍DN的增益&#xff0c;比如10变为20。 这与dB和线性增益的关系以及传感器处理流程有关。以下是具体原因分析&#xff1a; 1. dB与线性增益的换算关系 6dB对应的理论线性增益应为&…...