力扣 1161. 最大层内元素和

题目

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

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

示例

输入：root = [1,7,0,7,-8,null,null]
输出：2
解释：
第 1 层各元素之和为 1，
第 2 层各元素之和为 7 + 0 = 7，
第 3 层各元素之和为 7 + -8 = -1，
所以我们返回第 2 层的层号，它的层内元素之和最大。

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/maximum-level-sum-of-a-binary-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

方法1：BFS

Java实现

class Solution {
    
    public int maxLevelSum(TreeNode root) {
    
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        int res = -1, step = 1;
        int sum, max = Integer.MIN_VALUE;

        while (!q.isEmpty()) {
    
            sum = 0;
            int sz = q.size();
            for (int i = 0; i < sz; i++) {
    
                TreeNode cur = q.poll();
                sum += cur.val;
                if (cur.left != null) q.offer(cur.left);
                if (cur.right != null) q.offer(cur.right);
            }
            if (sum > max) {
    
                max = sum;
                res = step;
            }
            step++;
        }

        return res;
    }
}