1161. 最大层内元素和

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

题目

Given the root of a binary tree, the level of its root is 1, the level of its children is 2, and so on.

Return the smallest level x such that the sum of all the values of nodes at level x is maximal.

Example 1:

Input: root = [1,7,0,7,-8,null,null]

Output: 2

Explanation:

Level 1 sum = 1.

Level 2 sum = 7 + 0 = 7.

Level 3 sum = 7 + -8 = -1.

So we return the level with the maximum sum which is level 2.

Example 2:

Input: root = [989,null,10250,98693,-89388,null,null,null,-32127]

Output: 2

Constraints:

• The number of nodes in the tree is in the range [1, 104].
• -10^5 <= Node.val <= 10^5

题目大意

给你一个二叉树的根节点 root。设根节点位于二叉树的第 1 层，而根节点的子节点位于第 2 层，依此类推。

请返回层内元素之和 最大 的那几层（可能只有一层）的层号，并返回其中 最小 的那个。

示例 1：


输入： root = [1,7,0,7,-8,null,null]

输出： 2

解释：

第 1 层各元素之和为 1，

第 2 层各元素之和为 7 + 0 = 7，

第 3 层各元素之和为 7 + -8 = -1，

所以我们返回第 2 层的层号，它的层内元素之和最大。

示例 2：

输入： root = [989,null,10250,98693,-89388,null,null,null,-32127]

输出： 2

提示：

• 树中的节点数在 [1, 104]范围内
• -10^5 <= Node.val <= 10^5

解题思路

核心思想是使用 层序遍历（BFS） 来按层访问二叉树的每个节点，在每一层中，计算该层的节点值之和，并与当前的最大值比较，记录具有最大和的层号。

1. 初始化：

   • 使用一个队列存储每层的节点。
   • 初始化最大层和为 -Infinity，以及对应的层号。
   • 设置当前层号。

2. 层序遍历：

   • 每次遍历一层，取出队列中所有节点。
   • 累加该层的节点值，比较是否是当前的最大和。

3. 更新最大值：如果当前层和大于最大层和，则更新最大层和及其对应的层号。

4. 递进到下一层：把当前层节点的左右子节点加入队列，继续下一轮遍历。

5. 返回结果：遍历完成后，返回最大层和对应的层号。

复杂度分析

• 时间复杂度：O(n)，每个节点访问一次。
• 空间复杂度：O(w)，w 为树的最大宽度，队列存储某层的所有节点。

代码

/**
 * @param {TreeNode} root
 * @return {number}
 */
var maxLevelSum = function (root) {
	if (!root) return 0;

	let queue = [root]; // 队列初始化
	let maxSum = -Infinity; // 记录最大层和
	let maxLevel = 0; // 记录最大层的层号
	let currentLevel = 1; // 当前层号

	while (queue.length > 0) {
		let levelSum = 0; // 当前层的和
		let levelSize = queue.length; // 当前层的节点数量

		for (let i = 0; i < levelSize; i++) {
			const node = queue.shift(); // 取出当前层的节点
			levelSum += node.val; // 累加当前层的节点值
			if (node.left) queue.push(node.left); // 加入左子节点
			if (node.right) queue.push(node.right); // 加入右子节点
		}

		// 更新最大层和及其层号
		if (levelSum > maxSum) {
			maxSum = levelSum;
			maxLevel = currentLevel;
		}

		currentLevel++; // 进入下一层
	}

	return maxLevel;
};

相关题目

题号	标题	题解	标签	难度	力扣
2583	二叉树中的第 K 大层和	[✓]	树 广度优先搜索 二叉树 1+	🟠	🀄️ 🔗
2641	二叉树的堂兄弟节点 II	[✓]	树 深度优先搜索 广度优先搜索 2+	🟠	🀄️ 🔗