1161. 最大层内元素和
题目
给你一个二叉树的根节点 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
分析
题目要求返回第n层之内元素之和最大的最小层数，自上而下，第一次遇到最大元素之和就是最小的层，使用广度优先遍历，一层一层向下。
如果使用深度优先，需要一个数组来维护每层元素之和，和树的深度
题解
广度优先遍历
class Solution {
public int maxLevelSum(TreeNode root) {
// 返回层内元素之和最大的层号，且是最小的层号
// 广度优先遍历，一层一层向下，遇到最大值就记录层号（深度），返回最大值的层号，因为是从上向下遍历，如果没有更大值，那么当前的最大值就是最小层
// 队列，保存每一层的节点，队列是动态的，只保存一层的节点
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
// 树的深度、初始最大值、最大值的深度
int dept = 0;
int max = Integer.MIN_VALUE;// 这个max要取最小值，初始不能为0，因为题目要求可以出现负数
int max_dept = 0;
// 广度优先，将每一层依次入队，并依次遍历这个节点的左右子节点，作为下一层的父节点
while(!queue.isEmpty()){
// 获取上一层节点的子节点数量，就是这一轮需要遍历的
int size = queue.size();
dept++;
// 因为这不是递归，而是while循环，所以只有一个sum，初始时为0
int sum = 0;
for(int i = 0; i < size; i++){
// 取出一个节点，计入sum
TreeNode node = queue.poll();
sum += node.val;
// 将这个节点的左右子节点入队，用于下一层的遍历
if(node.left != null){
queue.offer(node.left);
}
if(node.right != null){
queue.offer(node.right);
}
}
// 自上而下，第一次遇到最大值就是最小的层号，不使用=>判断
// 因为题目要求计算各层元素之和，所以每层遍历完再计算最大值
if(sum > max){
max = sum;
max_dept = dept;
}
}
return max_dept;
}
}
深度优先遍历
class Solution {
private List<Integer> sum = new ArrayList<>();
public int maxLevelSum(TreeNode root) {
// 广度优先，利用数组，数组长度为树的层数，数组值为每层之和
dfs(root, 0);
int ans = 0;
for(int i = 0; i < sum.size(); i++){
if(sum.get(i) > sum.get(ans)){
ans = i;
}
}
return ans + 1;
}
// 深度优先
private void dfs(TreeNode node, int level){
if(level == sum.size()){
// 为什么直接加，每一层的第一个，每一个新的深度，因为之前没有所以直接add加，之后有了这个level，就可以get(level)+val了
sum.add(node.val);
}else{
// 根据level，取出之前的层数和，然后加上当前节点值，组合成每层之和
sum.set(level, sum.get(level) + node.val);
}
if(node.left != null){
dfs(node.left, level + 1);
}
if(node.right != null){
dfs(node.right, level + 1);
}
}
}
