1161. 最大层内元素和

难度中等84收藏分享切换为英文接收动态反馈

给你一个二叉树的根节点 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：

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

提示：

树中的节点数在 [1, 104]范围内
-105 <= Node.val <= 105

题解

二叉树的层序遍历的变形，注意遍历一层的时候可以首先获取队列的长度，然后递减指针，这样就可以遍历所有上一层的结点

遍历每一层的时候，累加该层的结点的值，保留最大的和以及对应的层数

最后返回最大的层数集合

/**
 * 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;
 *     }
 * }
 */
public class Solution {
    public int maxLevelSum(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        int max_sum = Integer.MIN_VALUE, max_level = 0, current_level = 0;
        while(!queue.isEmpty()) {
            int temp_sum = 0;
            for (int i = queue.size(); i > 0; i--) {
                TreeNode temp = queue.poll();
                temp_sum += temp.val;
                if (temp.left != null) queue.add(temp.left);
                if (temp.right != null) queue.add(temp.right);
            }
            current_level++;
            if (temp_sum > max_sum) {
                max_sum = temp_sum;
                max_level = current_level;
            }
        }
        return max_level;
    }
}