2583. 二叉树中的第 K 大层和

简介: 2583. 二叉树中的第 K 大层和

说在前面

🎈不知道大家对于算法的学习是一个怎样的心态呢?为了面试还是因为兴趣?不管是出于什么原因,算法学习需要持续保持。

题目描述

给你一棵二叉树的根节点 root 和一个正整数 k

树中的 层和 是指 同一层 上节点值的总和。

返回树中第 k 大的层和(不一定不同)。如果树少于 k 层,则返回 -1

注意,如果两个节点与根节点的距离相同,则认为它们在同一层。

示例 1:

输入: root = [5,8,9,2,1,3,7,4,6], k = 2
输出: 13
解释: 树中每一层的层和分别是:
- Level 1: 5
- Level 2: 8 + 9 = 17
- Level 3: 2 + 1 + 3 + 7 = 13
- Level 4: 4 + 6 = 10
第 2 大的层和等于 13 。

示例 2:

输入: root = [1,2,null,3], k = 1
输出: 3
解释: 最大的层和是 3 。

提示:

  • 树中的节点数为 n
  • 2 <= n <= 10^5
  • 1 <= Node.val <= 10^6
  • 1 <= k <= n

解题思路

首先我们需要先理解一下题意,题目要我们计算的是树的层和,如下图:

我们需要先计算出每一层的节点和,涉及到层级的话我们可以用层序遍历来解决题目:

  • 层序遍历通常使用队列(Queue)来实现。算法的基本思想是:
  • 1、将根节点入队。
  • 2、循环执行以下步骤直到队列为空:
  • 从队列中取出一个节点,并访问该节点。
  • 将该节点的子节点(如果有)依次入队。

通过这种方式,可以确保按照层级顺序逐层访问树的所有节点。层序遍历是一种广度优先搜索(Breadth-First Search,BFS)的应用,适用于需要按照层级结构处理树的问题。

获取到每一层级的节点和之后,我们进行排序找出第k大的和即可。

AC代码

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} k
 * @return {number}
 */
var kthLargestLevelSum = function (root, k) {
  const q = [{ node: root, floor: 1 }];
  const cnt = [];
  let ind = 0;
  while (ind < q.length) {
    const { node, floor } = q[ind];
    if (cnt.length < floor) cnt.push(0);
    cnt[floor - 1] += node.val;
    if (node.left) q.push({ node: node.left, floor: floor + 1 });
    if (node.right) q.push({ node: node.right, floor: floor + 1 });
    ind++;
  }
  if (cnt.length < k) return -1;
  return cnt.sort((a, b) => b - a)[k - 1];
};

公众号

关注公众号『前端也能这么有趣』,获取更多有趣内容。

说在后面

🎉 这里是 JYeontu,现在是一名前端工程师,有空会刷刷算法题,平时喜欢打羽毛球 🏸 ,平时也喜欢写些东西,既为自己记录 📋,也希望可以对大家有那么一丢丢的帮助,写的不好望多多谅解 🙇,写错的地方望指出,定会认真改进 😊,偶尔也会在自己的公众号『前端也能这么有趣』发一些比较有趣的文章,有兴趣的也可以关注下。在此谢谢大家的支持,我们下文再见 🙌。

目录
相关文章
|
机器学习/深度学习 存储 算法
深入理解【二叉树】
深入理解【二叉树】
89 0
|
C语言
【二叉树】的实现
【二叉树】的实现
39 0
|
3月前
|
算法
22_最大二叉树
22_最大二叉树
|
6月前
|
Java
二叉树
二叉树
26 0
二叉树(详解)下
二叉树(详解)
62 0
|
7月前
|
算法 网络协议 NoSQL
认识二叉树(详细介绍)
认识二叉树(详细介绍)
|
7月前
|
存储 数据库管理
【二叉树】
【二叉树】
53 0
|
7月前
|
存储
二叉树的实现(下)
二叉树的实现(下)
64 0
24 二叉树
24 二叉树
53 0
下一篇
DataWorks