Leetcode75 1161. 最大层内元素和

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

提示：

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

Solution 1

/**
 * 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) {
        int maxSum = Integer.MIN_VALUE;
        int result = 0;
        int depth = 0;
        List<TreeNode> layer = new LinkedList<>();
        List<TreeNode> next = new LinkedList<>();
        if (root != null) {
            layer.add(root);
        }
        while (!layer.isEmpty()) {
            depth++;
            int currSum = 0;
            for (TreeNode node : layer) {
                currSum += node.val;
                if (node.left != null) {
                    next.add(node.left);
                }
                if (node.right != null) {
                    next.add(node.right);
                }
            }
            if (currSum > maxSum) {
                maxSum = currSum;
                result = depth;
            }
            layer = next;
            next = new LinkedList<>();
        }
        return result;
    }
}