当前位置: 首页 > 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;开发有效的低光图像增强方法…...

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

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

(十)学生端搭建

本次旨在将之前的已完成的部分功能进行拼装到学生端&#xff0c;同时完善学生端的构建。本次工作主要包括&#xff1a; 1.学生端整体界面布局 2.模拟考场与部分个人画像流程的串联 3.整体学生端逻辑 一、学生端 在主界面可以选择自己的用户角色 选择学生则进入学生登录界面…...

HTML 列表、表格、表单

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

剑指offer20_链表中环的入口节点

链表中环的入口节点 给定一个链表&#xff0c;若其中包含环&#xff0c;则输出环的入口节点。 若其中不包含环&#xff0c;则输出null。 数据范围 节点 val 值取值范围 [ 1 , 1000 ] [1,1000] [1,1000]。 节点 val 值各不相同。 链表长度 [ 0 , 500 ] [0,500] [0,500]。 …...

【python异步多线程】异步多线程爬虫代码示例

claude生成的python多线程、异步代码示例&#xff0c;模拟20个网页的爬取&#xff0c;每个网页假设要0.5-2秒完成。 代码 Python多线程爬虫教程 核心概念 多线程&#xff1a;允许程序同时执行多个任务&#xff0c;提高IO密集型任务&#xff08;如网络请求&#xff09;的效率…...

Java线上CPU飙高问题排查全指南

一、引言 在Java应用的线上运行环境中&#xff0c;CPU飙高是一个常见且棘手的性能问题。当系统出现CPU飙高时&#xff0c;通常会导致应用响应缓慢&#xff0c;甚至服务不可用&#xff0c;严重影响用户体验和业务运行。因此&#xff0c;掌握一套科学有效的CPU飙高问题排查方法&…...

HarmonyOS运动开发:如何用mpchart绘制运动配速图表

##鸿蒙核心技术##运动开发##Sensor Service Kit&#xff08;传感器服务&#xff09;# 前言 在运动类应用中&#xff0c;运动数据的可视化是提升用户体验的重要环节。通过直观的图表展示运动过程中的关键数据&#xff0c;如配速、距离、卡路里消耗等&#xff0c;用户可以更清晰…...

初探Service服务发现机制

1.Service简介 Service是将运行在一组Pod上的应用程序发布为网络服务的抽象方法。 主要功能&#xff1a;服务发现和负载均衡。 Service类型的包括ClusterIP类型、NodePort类型、LoadBalancer类型、ExternalName类型 2.Endpoints简介 Endpoints是一种Kubernetes资源&#xf…...

MySQL 知识小结(一)

一、my.cnf配置详解 我们知道安装MySQL有两种方式来安装咱们的MySQL数据库&#xff0c;分别是二进制安装编译数据库或者使用三方yum来进行安装,第三方yum的安装相对于二进制压缩包的安装更快捷&#xff0c;但是文件存放起来数据比较冗余&#xff0c;用二进制能够更好管理咱们M…...

在Mathematica中实现Newton-Raphson迭代的收敛时间算法(一般三次多项式)

考察一般的三次多项式&#xff0c;以r为参数&#xff1a; p[z_, r_] : z^3 (r - 1) z - r; roots[r_] : z /. Solve[p[z, r] 0, z]&#xff1b; 此多项式的根为&#xff1a; 尽管看起来这个多项式是特殊的&#xff0c;其实一般的三次多项式都是可以通过线性变换化为这个形式…...