当前位置: 首页 > 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…...

SpringBoot-17-MyBatis动态SQL标签之常用标签

文章目录 1 代码1.1 实体User.java1.2 接口UserMapper.java1.3 映射UserMapper.xml1.3.1 标签if1.3.2 标签if和where1.3.3 标签choose和when和otherwise1.4 UserController.java2 常用动态SQL标签2.1 标签set2.1.1 UserMapper.java2.1.2 UserMapper.xml2.1.3 UserController.ja…...

Java 语言特性(面试系列1)

一、面向对象编程 1. 封装&#xff08;Encapsulation&#xff09; 定义&#xff1a;将数据&#xff08;属性&#xff09;和操作数据的方法绑定在一起&#xff0c;通过访问控制符&#xff08;private、protected、public&#xff09;隐藏内部实现细节。示例&#xff1a; public …...

Appium+python自动化(十六)- ADB命令

简介 Android 调试桥(adb)是多种用途的工具&#xff0c;该工具可以帮助你你管理设备或模拟器 的状态。 adb ( Android Debug Bridge)是一个通用命令行工具&#xff0c;其允许您与模拟器实例或连接的 Android 设备进行通信。它可为各种设备操作提供便利&#xff0c;如安装和调试…...

多场景 OkHttpClient 管理器 - Android 网络通信解决方案

下面是一个完整的 Android 实现&#xff0c;展示如何创建和管理多个 OkHttpClient 实例&#xff0c;分别用于长连接、普通 HTTP 请求和文件下载场景。 <?xml version"1.0" encoding"utf-8"?> <LinearLayout xmlns:android"http://schemas…...

如何在看板中体现优先级变化

在看板中有效体现优先级变化的关键措施包括&#xff1a;采用颜色或标签标识优先级、设置任务排序规则、使用独立的优先级列或泳道、结合自动化规则同步优先级变化、建立定期的优先级审查流程。其中&#xff0c;设置任务排序规则尤其重要&#xff0c;因为它让看板视觉上直观地体…...

服务器硬防的应用场景都有哪些?

服务器硬防是指一种通过硬件设备层面的安全措施来防御服务器系统受到网络攻击的方式&#xff0c;避免服务器受到各种恶意攻击和网络威胁&#xff0c;那么&#xff0c;服务器硬防通常都会应用在哪些场景当中呢&#xff1f; 硬防服务器中一般会配备入侵检测系统和预防系统&#x…...

Mac软件卸载指南,简单易懂!

刚和Adobe分手&#xff0c;它却总在Library里给你写"回忆录"&#xff1f;卸载的Final Cut Pro像电子幽灵般阴魂不散&#xff1f;总是会有残留文件&#xff0c;别慌&#xff01;这份Mac软件卸载指南&#xff0c;将用最硬核的方式教你"数字分手术"&#xff0…...

BCS 2025|百度副总裁陈洋:智能体在安全领域的应用实践

6月5日&#xff0c;2025全球数字经济大会数字安全主论坛暨北京网络安全大会在国家会议中心隆重开幕。百度副总裁陈洋受邀出席&#xff0c;并作《智能体在安全领域的应用实践》主题演讲&#xff0c;分享了在智能体在安全领域的突破性实践。他指出&#xff0c;百度通过将安全能力…...

听写流程自动化实践,轻量级教育辅助

随着智能教育工具的发展&#xff0c;越来越多的传统学习方式正在被数字化、自动化所优化。听写作为语文、英语等学科中重要的基础训练形式&#xff0c;也迎来了更高效的解决方案。 这是一款轻量但功能强大的听写辅助工具。它是基于本地词库与可选在线语音引擎构建&#xff0c;…...

GruntJS-前端自动化任务运行器从入门到实战

Grunt 完全指南&#xff1a;从入门到实战 一、Grunt 是什么&#xff1f; Grunt是一个基于 Node.js 的前端自动化任务运行器&#xff0c;主要用于自动化执行项目开发中重复性高的任务&#xff0c;例如文件压缩、代码编译、语法检查、单元测试、文件合并等。通过配置简洁的任务…...