(树) 剑指 Offer 54. 二叉搜索树的第k大节点 ——【Leetcode每日一题】

news/2024/2/28 11:42:15

❓剑指 Offer 54. 二叉搜索树的第k大节点

难度:简单

给定一棵二叉搜索树,请找出其中第 k 大的节点的值。

示例 1:

输入: root = [3,1,4,null,2], k = 13/ \1   4\2
输出: 4

示例 2:

输入: root = [5,3,6,2,4,null,null,1], k = 35/ \3   6/ \2   4/1
输出: 4

限制

  • 1 ≤ k ≤ 二叉搜索树元素个数

💡思路:中序遍历

找第 k 大的结点,二叉搜索树的中序遍历结果是从小到大排序:

  • 所以其实就是对二叉搜索树进行 倒过来的中序遍历
    • 遍历顺序为:右 -> 中 -> 左
    • 每遍历一个元素 k--,当 k = 0 时就是最终结果。

🍁代码:(C++、Java)

C++

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
private:int ans = 0;void inOrder(TreeNode* root, int& k){if(root == nullptr || k <= 0) return;inOrder(root->right, k);if(--k == 0){ans = root->val;return;}inOrder(root->left, k);}
public:int kthLargest(TreeNode* root, int k) {inOrder(root, k);return ans;}
};

Java

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode(int x) { val = x; }* }*/
class Solution {private int ans, k;private void inOrder(TreeNode root){if(root == null || k <= 0) return;inOrder(root.right);if(--k == 0){ans = root.val;return;}inOrder(root.left);}public int kthLargest(TreeNode root, int k) {this.k = k;inOrder(root);return ans;}
}

🚀 运行结果:

在这里插入图片描述

🕔 复杂度分析:

  • 时间复杂度 O ( n ) O(n) O(n),当树退化为链表时(全部为右子节点),无论 k 的值大小,递归深度都为 n ,占用 O ( n ) O(n) O(n) 时间。
  • 空间复杂度 O ( n ) O(n) O(n),当树退化为链表时(全部为右子节点),系统使用 O ( n ) O(n) O(n) 大小的栈空间。

题目来源:力扣。

放弃一件事很容易,每天能坚持一件事一定很酷,一起每日一题吧!
关注我LeetCode主页 / CSDN—力扣专栏,每日更新!

注: 如有不足,欢迎指正!


http://www.ppmy.cn/news/1014167.html

相关文章

Effective Java笔记(29)优先考虑泛型

一般来说 &#xff0c;将集合声 明参数化&#xff0c;以及使用 JDK 所提供的泛型方法&#xff0c;这些都不太困难 。编写自己的泛型会比较困难一些&#xff0c;但是值得花些时间去学习如何编写 。 以简单的&#xff08;玩具&#xff09;堆校实现为例 &#xff1a; // Object -…

有奖活动 | 大咖论道:一同畅聊鸿蒙生态

点击预约直播 活动简介 即日起-2023年9月5日&#xff0c;参与本期活动与大咖一起聊聊鸿蒙新生态&#xff0c;您可以在社区写下对鸿蒙生态的畅想&#xff0c;也可以学习相关课程并获取证书&#xff0c;完成活动任务即可参与精美礼品抽奖。 活动周期 8月1日-9月5日 参与考试 Harm…

冠达管理:A股三大指数震荡整理 机构看好反弹趋势延续

周一&#xff0c;沪深两市呈弱势震动格式&#xff0c;创业板指领跌。到收盘&#xff0c;上证综指跌0.59%&#xff0c;报3268.83点&#xff1b;深证成指跌0.83%&#xff0c;报11145.03点&#xff1b;创业板指跌1%&#xff0c;报2240.77点。 资金面上&#xff0c;沪深两市昨日合计…

Android WIFI-系统连接WIFI显示网络连接受限

问题描述 使用Android设备打开设置&#xff0c;选择WIFI输入正确密码连接&#xff0c;会显示已连接&#xff0c;无网络&#xff0c;然后变成网络连接受限&#xff0c;实际可以使用此WIFI进行上网。 问题分析 异常Log D NetworkMonitor/100: PROBE_DNS www.google.com 107ms O…

八年级编程代码必考题,八年级编程猫教学设计

大家好&#xff0c;小编来为大家解答以下问题&#xff0c;八年级编程哪个内容适合上公开课&#xff0c;八年级编程猫教学设计&#xff0c;现在让我们一起来看看吧&#xff01; 算术运算符与表达式 课题 算术运算符 与表达式 单元 Python程序设计基础 学科 信息 年级 八年级 主备…

国内大模型在局部能力上已超ChatGPT

中文大模型正在后来居上&#xff0c;也必须后来居上。 数科星球原创 作者丨苑晶 编辑丨大兔 从GPT3.5彻底出圈后&#xff0c;大模型的影响力开始蜚声国际。一段时间内&#xff0c;国内科技公司可谓被ChatGPT按在地上打&#xff0c;毫无还手之力。 彼时&#xff0c;很多企业…

rman常用命令

查看时间段需要恢复的归档 RMAN> list backup of archivelog time between "to_date(2023-08-02 00:10:00,yyyy-mm-dd,hh24:mi:ss)" and "to_date(2023-08-02 03:03:03,yyyy-mm-dd hh24:mi:ss)"; #加载不在控制文件记录中的归档&#xff0c;并删除6小时…

同芯同意创未来——赛意力量 SNP ·南京半导体高科专场

7月28日&#xff0c;“赛意力量全国行”将在南京组织以“同芯同意创未来”为主题的南京半导体高科专场沙龙活动。届时&#xff0c;“赛意力量”将携众优秀企业IT及财务领域嘉宾&#xff0c;开展深度交流&#xff0c;共同为推动科技创新与区域经济发展而出谋划策。 南京作为中国…

如何创建51单片机KEIL工程

如何创建51单片机KEIL工程步骤&#xff1a; &#xff08;1&#xff09;打开keil软件&#xff0c;点击工具栏-Project&#xff0c;选择创建新的工程&#xff1b; &#xff08;2&#xff09;然后给工程命名&#xff0c;文章以project为例&#xff0c;然后点击保存 &#xff08…

Vivado中SmartConnect和InterConnect的区别

前言&#xff1a;本文章为FPGA问答系列&#xff0c;我们会定期整理FPGA交流群&#xff08;包括其他FPGA博主的群&#xff09;里面有价值的问题&#xff0c;并汇总成文章&#xff0c;如果问题多的话就每周整理一期&#xff0c;如果问题少就每两周整理一期&#xff0c;一方面是希…

嵌入式Linux下LVGL的移植与配置

一.sdk源码下载路径 1.官方源码下载路径如下: ​​​​​​ https://github.com/lvgl/lvgl git下载方式 git clone https://github.com/lvgl/lvgl.git 2.个人移植好的源码8.2版本下载路径: 链接:https://pan.baidu.com/s/1jyqIennsQpv-RB4RyKvZyg?pwd=c68e 提取码:c68e…

模型训练技术指南

目录 引言 1. 模型训练的重要性 2. 数据预处理 3. 特征工程 4. 模型选择与评估 5. 参数调优 6. 模型集成 7. 过拟合与欠拟合 8. 模型保存与加载 9. 分布式训练与加速 10. 最佳实践与常见问题 引言 模型训练是机器学习领域中至关重要的一步&#xff0c;它决定了模型的…

如何运营手游联运平台游戏?

运营手游联运平台游戏需要综合考虑多个方面&#xff0c;包括游戏选择、合作伙伴、市场推广、用户运营等。以下是运营手游联运平台游戏的一些建议&#xff1a; 游戏选择&#xff1a;选择优质的手游&#xff0c;确保游戏的品质和内容能够吸引玩家&#xff0c;满足市场需求。 合…

微信小程序中背景图片如何占满整个屏幕,拉伸

不变形 1. 在页面的wxss文件中&#xff0c;设置背景图片的样式&#xff1a; page{background-image: url(图片路径);background-size: 100% 100%;background-repeat: no-repeat; }2. 在页面的json文件中&#xff0c;设置背景图片的样式&#xff1a; {"backgroundTextStyl…

Android平台一对一音视频通话方案对比:WebRTC VS RTMP VS RTSP

一对一音视频通话使用场景 一对一音视频通话都需要稳定、清晰和流畅&#xff0c;以确保良好的用户体验&#xff0c;常用的使用场景如下&#xff1a; 社交应用&#xff1a;社交应用是一种常见的使用场景&#xff0c;用户可以通过音视频通话进行面对面的交流&#xff1b;在线教…

如何将安卓 Gradle 模块打包发布到本地 Maven 仓库

文章目录 具体流程 笔者的运行环境&#xff1a; Android Studio Flamingo | 2022.2.1 Android SDK 33 Gradle 8.0.1 JDK 17 Android 的 Gradle 项目与一般的 Gradle 项目是不同的&#xff0c;因此对将 Gradle 模块打包发布到本地 Maven 仓库来说&#xff0c;对普通 Gradle …

Jenkins+Nginx+vue

安装nodejs 在这里插入图片描述 echo off xcopy C:\ProgramData\Jenkins\.jenkins\workspace\super_manage_vue\dist F:\java\www\super_manage_vue\ /s /e /y echo 复制文件完成 exit安装niginx 配置文件如下 #user nobody; worker_processes 1;#error_log logs/error.lo…

mxgraph的核心元素详谈

前言: MxGraph是一个流行的开源图形库,它提供了一stop solution for creating graphical representations of data。下面是MxGraph的核心源码讲解: 正文: Graph Structure(图结构): MxGraph将一个图表示为一个层次结构,由节点和边组成。节点表示图中的顶点,而边表示它…

docker安装neo4j

参考文章&#xff1a; 1、Mac 本地以 docker 方式配置 neo4j_neo4j mac docker_Abandon_first的博客-CSDN博客 2、https://www.cnblogs.com/caoyusang/p/13610408.html 安装的时候&#xff0c;参考了以上文章。遇到了一些问题&#xff0c;记录下自己的安装过程&#xff1a; …

Linux命令查看文件和文件夹内存空间大小 du -sh

1. du -sh 查看文件&#xff0c;文件夹空间大小 1.1 du&#xff1a; disk usage 1.2 -s&#xff1a;表示以总结&#xff08;summary&#xff09;的方式显示结果&#xff0c;只显示总大小 1.3 -h: 表示以人类&#xff08;human&#xff09;可读的格式显示结果 2. 查看项目总…
最新文章