题解 | #重量级的一层#
重量级的一层
https://www.nowcoder.com/practice/193372871b09426ab9ea805f0fd44d5c
一、知识点:
BFS、遍历、二叉树
二、文字分析:
使用了广度优先搜索(BFS)算法来遍历二叉树的每一层,并计算每一层牛的总重量。我们使用一个队列来保存当前层的节点,并在遍历完当前层后,计算该层牛的总重量。如果当前层的牛的总重量大于等于当前找到的最大层的牛的总重量,我们更新最大层的牛的总重量和对应的层数。最后,返回最大层的层数即可。
时间复杂度为 O(N),空间复杂度为 O(N)。
三、编程语言:
java
四、正确代码:
import java.util.*;
/*
* public class TreeNode {
* int val = 0;
* TreeNode left = null;
* TreeNode right = null;
* public TreeNode(int val) {
* this.val = val;
* }
* }
*/
public class Solution {
public int maxLevelSum(TreeNode root) {
if (root == null) {
return 0;
}
int maxLevelSum = root.val; // 当前找到的最大层的牛的总重量
int maxLevel = 1; // 当前找到的最大层的层数
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
int level = 1; // 当前处理的层
while (!queue.isEmpty()) {
int size = queue.size();
int currentLevelSum = 0; // 当前层的牛的总重量
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
currentLevelSum += node.val;
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
if (currentLevelSum >= maxLevelSum) {
maxLevelSum = currentLevelSum;
maxLevel = level;
}
level++;
}
return maxLevel;
}
}
