一、知识点:
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; } }