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

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 题目来源&#xff1a;2583. 二叉树中的第 K 大层和 解法1&#xff1a;层序遍历 排序 先使用层序遍历计算出树的每一层的节点值的和&#xff0c;保存在数组 levelSum 中。然后将数组进行排序&#xff0c;返回第 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 及其应 参考答案&#xff1a; 参考答案&#xff1a; 所谓 BFC&#xff0c;指的是一个独立的布局环境&#xff0c;BFC 内部的元素布局与外部互不影响。 触发 BFC 的方式有很多&#xff0c;常见的有&#xff1a; 设置浮动overflow 设置为 auto、scr…...

定制你的【Spring Boot Starter】,加速开发效率

摘要&#xff1a; 本文将介绍如何创建一个自定义的 Spring Boot Starter&#xff0c;让您可以封装常用功能和配置&#xff0c;并在多个 Spring Boot 项目中共享和重用。 1. 简介 Spring Boot Starter 是 Spring Boot 框架中的一种特殊的依赖项&#xff0c;它用于快速启动和配置…...

Vue源码系列讲解——生命周期篇【二】(new Vue)

目录 1. 前言 2. new Vue()都干了什么 3 . 合并属性 4. callHook函数如何触发钩子函数 5. 总结 1. 前言 上篇文章中介绍了Vue实例的生命周期大致分为4个阶段&#xff0c;那么首先我们先从第一个阶段——初始化阶段开始入手分析。从生命周期流程图中我们可以看到&#xff…...

JavaScript 设计模式之观察者模式

观察者模式 观察者模式又被称为发布-订阅模式&#xff0c;使用一个对象来收集订阅者&#xff0c;在发布时遍历所有订阅者&#xff0c;然后将信息传递给订阅者&#xff0c;可以这样来实现一个简单的模式 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人职匹配推荐系统 获取源码——》公主号&#xff1a;计算机专业毕设大全...

【笔记】【开发方案】APN 配置参数 bitmask 数据转换(Android KaiOS)

一、参数说明 &#xff08;一&#xff09;APN配置结构对比 平台AndroidKaiOS文件类型xmljson结构每个<apn>标签是一条APN&#xff0c;包含完成的信息层级数组结构&#xff0c;使用JSON格式的数据。最外层是mcc&#xff0c;其次mnc&#xff0c;最后APN用数组形式配置&am…...

Redis篇之缓存雪崩、击穿、穿透详解

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

【深度学习笔记】3_2线性回归的从零实现

注&#xff1a;本文为《动手学深度学习》开源内容&#xff0c;仅为个人学习记录&#xff0c;无抄袭搬运意图 3.2 线性回归的从零开始实现 在了解了线性回归的背景知识之后&#xff0c;现在我们可以动手实现它了。尽管强大的深度学习框架可以减少大量重复性工作&#xff0c;但若…...

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&#xff0c;参数接收方式采用RequestBody和RequestParam&#…...

直接插入排序+希尔排序+冒泡排序+快速排序+选择排序+堆排序+归并排序+基于统计的排序

插入排序&#xff1a;直接插入排序、希尔排序 交换排序&#xff1a;冒泡排序、快速排序 选择排序&#xff1a;简单选择排序、堆排序 其他&#xff1a;归并排序、基于统计的排序 一、直接插入排序 #include<stdio.h> #include<stdlib.h> /* 直接插入排序&#…...

Java高级 / 架构师 场景方案 面试题(二)

1.双十一亿级用户日活统计如何用 Redis快速计算 在双十一这种亿级用户日活统计的场景中&#xff0c;使用Redis进行快速计算的关键在于利用Redis的数据结构和原子操作来高效地统计和计算数据。以下是一个基于Redis的日活统计方案&#xff1a; 选择合适的数据结构&#xff1a; …...

C/C++内存管理学习【new】

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

选择适合你的编程语言

引言 在当今瞬息万变的技术领域中&#xff0c;选择一门合适的编程语言对于个人职业发展和技术成长至关重要。每种语言都拥有独特的设计哲学、应用场景和市场需求&#xff0c;因此&#xff0c;在决定投入时间和精力去学习哪种编程语言时&#xff0c;我们需要综合分析多个因素&a…...

【力扣每日一题】力扣106从中序和后序遍历序列构造二叉树

题目来源 力扣106从中序和后序遍历序列构造二叉树 题目概述 给定两个整数数组 inorder 和 postorder &#xff0c;其中 inorder 是二叉树的中序遍历&#xff0c; postorder 是同一棵树的后序遍历&#xff0c;请你构造并返回这颗 二叉树 。 思路分析 后序遍历序列的最末尾数…...

logback日志回滚原理

日志输出主要依赖RollingFileAppender、TimeBasedRollingPolicy、SizeAndTimeBasedFNATP。 RollingFileAppender 主要用于生成日志文件&#xff0c;格式化内容再输出到日志文件TimeBasedRollingPolicy 设置回滚策略&#xff0c;如果发现日志输出的时间超过单位时间&#xff0c…...

[C#]winform基于opencvsharp结合pairlie算法实现低光图像增强黑暗图片变亮变清晰

【低光图像增强介绍】 在图像处理领域&#xff0c;低光图像增强是一个具有挑战性的任务。由于光线不足&#xff0c;这些图像往往呈现出低对比度、高噪声和细节丢失等问题&#xff0c;严重影响了图像的视觉效果和后续分析的准确性。因此&#xff0c;开发有效的低光图像增强方法…...

idea大量爆红问题解决

问题描述 在学习和工作中&#xff0c;idea是程序员不可缺少的一个工具&#xff0c;但是突然在有些时候就会出现大量爆红的问题&#xff0c;发现无法跳转&#xff0c;无论是关机重启或者是替换root都无法解决 就是如上所展示的问题&#xff0c;但是程序依然可以启动。 问题解决…...

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 的描述&#xff0c;后续 TensorRT-LLM 团队可能更专注于更新和维护 pytorch backend。但 tensorrt backend 作为先前一直开发的工作&#xff0c;其中包含了大量可以学习的地方。本文主要看看它导出模型的部分&#x…...

HTML 列表、表格、表单

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

Python实现prophet 理论及参数优化

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

ESP32 I2S音频总线学习笔记(四): INMP441采集音频并实时播放

简介 前面两期文章我们介绍了I2S的读取和写入&#xff0c;一个是通过INMP441麦克风模块采集音频&#xff0c;一个是通过PCM5102A模块播放音频&#xff0c;那如果我们将两者结合起来&#xff0c;将麦克风采集到的音频通过PCM5102A播放&#xff0c;是不是就可以做一个扩音器了呢…...

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 推荐理由&#xff1a;大部分的转换软件需要收费&#xff0c;要么功能不齐全&#xff0c;而开会员又用不了几次浪费钱&#xff0c;借用别人的又不安全。 这个网站它不需要登录或下载安装。而且提供的免费功能就能满足日常…...

LCTF液晶可调谐滤波器在多光谱相机捕捉无人机目标检测中的作用

中达瑞和自2005年成立以来&#xff0c;一直在光谱成像领域深度钻研和发展&#xff0c;始终致力于研发高性能、高可靠性的光谱成像相机&#xff0c;为科研院校提供更优的产品和服务。在《低空背景下无人机目标的光谱特征研究及目标检测应用》这篇论文中提到中达瑞和 LCTF 作为多…...

CSS3相关知识点

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