力扣---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

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

深度优先和广度优先都可以做。

深度优先需要用一个 list 来存储每一层的累加和。

广度优先需要维护一个最大值以及最大值所处层数。

深度优先：

class Solution {
    public int maxLevelSum (TreeNode root) {
        // 存储每一层的累加和。
        List<Integer> list = new ArrayList<>();
        dfs(root, 0, list);
        int max = Integer.MIN_VALUE;
        int res = -1;
        // 寻找最大值所在的层数。
        for (int i = 0; i < list.size(); i ++) {
            int sum = list.get(i);
            if (sum > max) {
                max = sum;
                res = i;
            }
        }
        return res + 1;
    }

    private void dfs (TreeNode node, int deepth, List<Integer> list) {
        if (node == null) {
            return;
        }
        // 遇到了新的一层。
        if (deepth >= list.size()) {
            list.add(node.val);
        } else {
            list.set(deepth, list.get(deepth) + node.val);
        }
        dfs(node.left, deepth + 1, list);
        dfs(node.right, deepth + 1, list);
    }
}

 广度优先：

class Solution {
    public int maxLevelSum (TreeNode root) {
        int max = Integer.MIN_VALUE;
        int res = -1;
        Deque<TreeNode> deque = new ArrayDeque<>();
        deque.addLast(root);
        int count = 1;
        while (!deque.isEmpty()) {
            int len = deque.size();
            int sum = 0;
            for (int i = 0; i < len; i++) {
                TreeNode temNode = deque.removeFirst();
                sum += temNode.val;
                if (temNode.left != null) {
                    deque.addLast(temNode.left);
                }
                if (temNode.right != null) {
                    deque.addLast(temNode.right);
                }
            }
            if (sum > max) {
                max = sum;
                res = count;
            }
            count++;
        }
        return res;
    }
}