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

🟠   🔖  树 广度优先搜索 二叉树 排序  🔗 力扣 LeetCode

题目

You are given the root of a binary tree and a positive integer k.

The level sum in the tree is the sum of the values of the nodes that are on the same level.

Return thekth largest level sum in the tree (not necessarily distinct). If there are fewer than k levels in the tree, return -1.

Note that two nodes are on the same level if they have the same distance from the root.

Example 1:

Input: root = [5,8,9,2,1,3,7,4,6], k = 2

Output: 13

Explanation: The level sums are the following:

• Level 1: 5.
• Level 2: 8 + 9 = 17.
• Level 3: 2 + 1 + 3 + 7 = 13.
• Level 4: 4 + 6 = 10.

The 2nd largest level sum is 13.

Example 2:

Input: root = [1,2,null,3], k = 1

Output: 3

Explanation: The largest level sum is 3.

Constraints:

• The number of nodes in the tree is n.
• 2 <= n <= 10^5
• 1 <= Node.val <= 10^6
• 1 <= k <= n

题目大意

给你一棵二叉树的根节点 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

解题思路

1. 宽度优先搜索（BFS）：使用 BFS 遍历二叉树，计算同一层上节点的层和。

2. 收集路径和：在遍历过程中，将每一层的层和存储在一个数组中。

3. 排序并选择：对层和进行降序排序，以找到第 k 大的层和。

4. 边界条件：注意如果树少于 k 层，则返回 -1。

复杂度分析

• 时间复杂度：O(n log n)，其中 n 是树中节点的数量。BFS 的遍历时间为 O(n)，然后对路径和进行排序需要 O(n log n) 的时间。
• 空间复杂度：O(n)，用于存储路径和的数组。

代码

/**
 * @param {TreeNode} root
 * @param {number} k
 * @return {number}
 */
var kthLargestLevelSum = function (root, k) {
	let queue = [root],
		levelSum = [];

	// BFS
	while (queue.length) {
		const len = queue.length;
		let sum = 0;
		for (let i = 0; i < len; i++) {
			const node = queue.shift();
			sum += node.val;
			if (node.left) queue.push(node.left);
			if (node.right) queue.push(node.right);
		}
		levelSum.push(sum);
	}
	// 如果树少于 k 层，则返回 -1
	if (levelSum.length < k) return -1;

	// 按降序排序，返回第 k 大的层和
	return levelSum.sort((a, b) => b - a)[k - 1];
};

相关题目

题号	标题	题解	标签	难度
144	二叉树的前序遍历	[✓]	栈 树 深度优先搜索 1+
1161	最大层内元素和		树 深度优先搜索 广度优先搜索 1+
3157	找到具有最小和的树的层数 🔒		树 深度优先搜索 广度优先搜索 1+