Leetcode2583. 二叉树中的第 K 大层和
Every day a Leetcode
题目来源:2583. 二叉树中的第 K 大层和
解法1:层序遍历 + 排序
先使用层序遍历计算出树的每一层的节点值的和,保存在数组 levelSum 中。然后将数组进行排序,返回第 k 大的值。需要考虑数组长度小于 k 的边界情况。
代码:
/** @lc app=leetcode.cn id=2583 lang=cpp** [2583] 二叉树中的第 K 大层和*/// @lc code=start
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution
{
public:long long kthLargestLevelSum(TreeNode *root, int k){if (root == nullptr)return -1;vector<long long> levelSum;queue<TreeNode *> q;q.push(root);while (!q.empty()){int size = q.size();long long sum = 0LL;for (int i = 0; i < size; i++){TreeNode *node = q.front();q.pop();sum += node->val;if (node->left)q.push(node->left);if (node->right)q.push(node->right);}levelSum.push_back(sum);}if (levelSum.size() < k)return -1;sort(levelSum.begin(), levelSum.end());return levelSum[levelSum.size() - k];}
};
// @lc code=end
结果:
复杂度分析:
时间复杂度:O(nlogn),其中 n 是二叉树的节点个数。
空间复杂度:O(n),其中 n 是二叉树的节点个数。
解法2:层序遍历 + 快速选择
也可以使用快速选择的算法快速定位第 k 大的元素。
代码:
// 层序遍历 + 快速选择class Solution
{
public:long long kthLargestLevelSum(TreeNode *root, int k){if (root == nullptr)return -1;vector<long long> levelSum;queue<TreeNode *> q;q.push(root);while (!q.empty()){int size = q.size();long long sum = 0LL;for (int i = 0; i < size; i++){TreeNode *node = q.front();q.pop();sum += node->val;if (node->left)q.push(node->left);if (node->right)q.push(node->right);}levelSum.push_back(sum);}int n = levelSum.size();if (k > n)return -1;ranges::nth_element(levelSum, levelSum.begin() + (n - k));return levelSum[n - k];}
};
结果:
复杂度分析:
时间复杂度:O(nlogn),其中 n 是二叉树的节点个数。
空间复杂度:O(n),其中 n 是二叉树的节点个数。
相关文章:

Leetcode2583. 二叉树中的第 K 大层和
Every day a Leetcode 题目来源:2583. 二叉树中的第 K 大层和 解法1:层序遍历 排序 先使用层序遍历计算出树的每一层的节点值的和,保存在数组 levelSum 中。然后将数组进行排序,返回第 k 大的值。需要考虑数组长度小于 k 的边…...

(六)激光线扫描-三维重建
本篇文章是《激光线扫描-三维重建》系列的最后一篇。 1. 基础理论 1.1 光平面 在之前光平面标定的文章中,已经提到过了,是指 激光发射器投射出一条线,形成的一个扇形区域平面就是光平面。 三维空间中平面的公式是: A X + B Y + C Z + D = 0 A X+B Y+C Z+D=0...

CSS 面试题汇总
CSS 面试题汇总 1. 介绍下 BFC 及其应 参考答案: 参考答案: 所谓 BFC,指的是一个独立的布局环境,BFC 内部的元素布局与外部互不影响。 触发 BFC 的方式有很多,常见的有: 设置浮动overflow 设置为 auto、scr…...

定制你的【Spring Boot Starter】,加速开发效率
摘要: 本文将介绍如何创建一个自定义的 Spring Boot Starter,让您可以封装常用功能和配置,并在多个 Spring Boot 项目中共享和重用。 1. 简介 Spring Boot Starter 是 Spring Boot 框架中的一种特殊的依赖项,它用于快速启动和配置…...
Vue源码系列讲解——生命周期篇【二】(new Vue)
目录 1. 前言 2. new Vue()都干了什么 3 . 合并属性 4. callHook函数如何触发钩子函数 5. 总结 1. 前言 上篇文章中介绍了Vue实例的生命周期大致分为4个阶段,那么首先我们先从第一个阶段——初始化阶段开始入手分析。从生命周期流程图中我们可以看到ÿ…...
JavaScript 设计模式之观察者模式
观察者模式 观察者模式又被称为发布-订阅模式,使用一个对象来收集订阅者,在发布时遍历所有订阅者,然后将信息传递给订阅者,可以这样来实现一个简单的模式 const Observable (function () {let __messages {}return {register:…...

数据结构D4作业
1.实现单向循环链表的功能 loop.c #include "loop.h" loop_p create_loop() { loop_p H(loop_p)malloc(sizeof(loop)); if(HNULL) { printf("创建失败\n"); return NULL; } H->len0; H->nextH; ret…...

springboot750人职匹配推荐系统
springboot750人职匹配推荐系统 获取源码——》公主号:计算机专业毕设大全...

【笔记】【开发方案】APN 配置参数 bitmask 数据转换(Android KaiOS)
一、参数说明 (一)APN配置结构对比 平台AndroidKaiOS文件类型xmljson结构每个<apn>标签是一条APN,包含完成的信息层级数组结构,使用JSON格式的数据。最外层是mcc,其次mnc,最后APN用数组形式配置&am…...

Redis篇之缓存雪崩、击穿、穿透详解
学习材料:https://xiaolincoding.com/redis/cluster/cache_problem.html 缓存雪崩 什么是缓存雪崩 在面对业务量较大的查询场景时,会把数据库中的数据缓存至redis中,避免大量的读写请求同时访问mysql客户端导致系统崩溃。这种情况下&#x…...

【深度学习笔记】3_2线性回归的从零实现
注:本文为《动手学深度学习》开源内容,仅为个人学习记录,无抄袭搬运意图 3.2 线性回归的从零开始实现 在了解了线性回归的背景知识之后,现在我们可以动手实现它了。尽管强大的深度学习框架可以减少大量重复性工作,但若…...
Apache Maven简介
Maven 简介 Apache Maven 是一个用于项目构建、依赖管理和项目信息管理的强大工具。它基于项目对象模型(Project Object Model,POM)进行构建,通过描述项目的结构和依赖关系来管理项目的构建过程。 以下是 Apache Maven 的一些关键原理和工作流程: 项目对象模型(POM)…...
#12解决request中getReader()和getInputStream()只能调用一次的问题
目录 1、背景 2、解决方案 2.1、自定义HttpServletRequestWrapper 2.2、JsonRequestHeaderParamsHelper 2.3、HttpServletRequestReplacedFilter 2.4、使用 1、背景 当前系统Content-Type为application/json,参数接收方式采用RequestBody和RequestParam&#…...
直接插入排序+希尔排序+冒泡排序+快速排序+选择排序+堆排序+归并排序+基于统计的排序
插入排序:直接插入排序、希尔排序 交换排序:冒泡排序、快速排序 选择排序:简单选择排序、堆排序 其他:归并排序、基于统计的排序 一、直接插入排序 #include<stdio.h> #include<stdlib.h> /* 直接插入排序&#…...
Java高级 / 架构师 场景方案 面试题(二)
1.双十一亿级用户日活统计如何用 Redis快速计算 在双十一这种亿级用户日活统计的场景中,使用Redis进行快速计算的关键在于利用Redis的数据结构和原子操作来高效地统计和计算数据。以下是一个基于Redis的日活统计方案: 选择合适的数据结构: …...

C/C++内存管理学习【new】
文章目录 一、C/C内存分布二、C语言中动态内存管理方式:malloc/calloc/realloc/free三、C内存管理方式3.1 new/delete操作内置类型3.2 new和delete操作自定义类型四、operator new与operator delete函数五、new和delete的实现原理5.1 内置类型 六、定位new表达式(pl…...

选择适合你的编程语言
引言 在当今瞬息万变的技术领域中,选择一门合适的编程语言对于个人职业发展和技术成长至关重要。每种语言都拥有独特的设计哲学、应用场景和市场需求,因此,在决定投入时间和精力去学习哪种编程语言时,我们需要综合分析多个因素&a…...
【力扣每日一题】力扣106从中序和后序遍历序列构造二叉树
题目来源 力扣106从中序和后序遍历序列构造二叉树 题目概述 给定两个整数数组 inorder 和 postorder ,其中 inorder 是二叉树的中序遍历, postorder 是同一棵树的后序遍历,请你构造并返回这颗 二叉树 。 思路分析 后序遍历序列的最末尾数…...
logback日志回滚原理
日志输出主要依赖RollingFileAppender、TimeBasedRollingPolicy、SizeAndTimeBasedFNATP。 RollingFileAppender 主要用于生成日志文件,格式化内容再输出到日志文件TimeBasedRollingPolicy 设置回滚策略,如果发现日志输出的时间超过单位时间,…...

[C#]winform基于opencvsharp结合pairlie算法实现低光图像增强黑暗图片变亮变清晰
【低光图像增强介绍】 在图像处理领域,低光图像增强是一个具有挑战性的任务。由于光线不足,这些图像往往呈现出低对比度、高噪声和细节丢失等问题,严重影响了图像的视觉效果和后续分析的准确性。因此,开发有效的低光图像增强方法…...

idea大量爆红问题解决
问题描述 在学习和工作中,idea是程序员不可缺少的一个工具,但是突然在有些时候就会出现大量爆红的问题,发现无法跳转,无论是关机重启或者是替换root都无法解决 就是如上所展示的问题,但是程序依然可以启动。 问题解决…...
Oracle查询表空间大小
1 查询数据库中所有的表空间以及表空间所占空间的大小 SELECTtablespace_name,sum( bytes ) / 1024 / 1024 FROMdba_data_files GROUP BYtablespace_name; 2 Oracle查询表空间大小及每个表所占空间的大小 SELECTtablespace_name,file_id,file_name,round( bytes / ( 1024 …...

(二)TensorRT-LLM | 模型导出(v0.20.0rc3)
0. 概述 上一节 对安装和使用有个基本介绍。根据这个 issue 的描述,后续 TensorRT-LLM 团队可能更专注于更新和维护 pytorch backend。但 tensorrt backend 作为先前一直开发的工作,其中包含了大量可以学习的地方。本文主要看看它导出模型的部分&#x…...

HTML 列表、表格、表单
1 列表标签 作用:布局内容排列整齐的区域 列表分类:无序列表、有序列表、定义列表。 例如: 1.1 无序列表 标签:ul 嵌套 li,ul是无序列表,li是列表条目。 注意事项: ul 标签里面只能包裹 li…...

Python实现prophet 理论及参数优化
文章目录 Prophet理论及模型参数介绍Python代码完整实现prophet 添加外部数据进行模型优化 之前初步学习prophet的时候,写过一篇简单实现,后期随着对该模型的深入研究,本次记录涉及到prophet 的公式以及参数调优,从公式可以更直观…...

ESP32 I2S音频总线学习笔记(四): INMP441采集音频并实时播放
简介 前面两期文章我们介绍了I2S的读取和写入,一个是通过INMP441麦克风模块采集音频,一个是通过PCM5102A模块播放音频,那如果我们将两者结合起来,将麦克风采集到的音频通过PCM5102A播放,是不是就可以做一个扩音器了呢…...

IoT/HCIP实验-3/LiteOS操作系统内核实验(任务、内存、信号量、CMSIS..)
文章目录 概述HelloWorld 工程C/C配置编译器主配置Makefile脚本烧录器主配置运行结果程序调用栈 任务管理实验实验结果osal 系统适配层osal_task_create 其他实验实验源码内存管理实验互斥锁实验信号量实验 CMISIS接口实验还是得JlINKCMSIS 简介LiteOS->CMSIS任务间消息交互…...

【分享】推荐一些办公小工具
1、PDF 在线转换 https://smallpdf.com/cn/pdf-tools 推荐理由:大部分的转换软件需要收费,要么功能不齐全,而开会员又用不了几次浪费钱,借用别人的又不安全。 这个网站它不需要登录或下载安装。而且提供的免费功能就能满足日常…...
LCTF液晶可调谐滤波器在多光谱相机捕捉无人机目标检测中的作用
中达瑞和自2005年成立以来,一直在光谱成像领域深度钻研和发展,始终致力于研发高性能、高可靠性的光谱成像相机,为科研院校提供更优的产品和服务。在《低空背景下无人机目标的光谱特征研究及目标检测应用》这篇论文中提到中达瑞和 LCTF 作为多…...

CSS3相关知识点
CSS3相关知识点 CSS3私有前缀私有前缀私有前缀存在的意义常见浏览器的私有前缀 CSS3基本语法CSS3 新增长度单位CSS3 新增颜色设置方式CSS3 新增选择器CSS3 新增盒模型相关属性box-sizing 怪异盒模型resize调整盒子大小box-shadow 盒子阴影opacity 不透明度 CSS3 新增背景属性ba…...