A.每日一题——1161. 最大层内元素和

题目链接：1161. 最大层内元素和（中等）

算法原理：

解法：层序遍历

9ms击败53.81%

时间复杂度O(N)

思路很简单，就是层序遍历的同时统计一下每层元素的和，然后利用顺序表找到对应最大值所在层数即可

层序遍历利用队列实现：

先将根节点扔进队列里，然后只要队列不空就持续以下循环👇

①计算该节点的子节点数

②将该节点的元素累加进sum

③将该节点的左右节点放进去作为下一层的各个子根节点

④该层节点元素累加结束后，将总和sum加入顺序表list

Java代码：

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public int maxLevelSum(TreeNode root) { //一次层序遍历即可 Queue<TreeNode> q=new LinkedList<>(); q.offer(root); List<Integer> list=new ArrayList<>(); while(!q.isEmpty()){ int sum=0; //计算一下当前层多少个数据 int size=q.size(); while(size!=0){ TreeNode cur=q.poll(); sum+=cur.val; if(cur.left!=null) q.offer(cur.left); if(cur.right!=null) q.offer(cur.right); size--; } //加入当前层元素和 list.add(sum); } //找每层元素和的最大值 int max=-0x3f3f3f3f; for(int x:list) max=Math.max(max,x); for(int i=0;i<list.size();i++) if(list.get(i)==max) return i+1; //照顾编译器 return -1; } }