LeetCode # 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

分析

题目要求返回第n层之内元素之和最大的最小层数，自上而下，第一次遇到最大元素之和就是最小的层，使用广度优先遍历，一层一层向下。
如果使用深度优先，需要一个数组来维护每层元素之和，和树的深度

题解

广度优先遍历

class Solution {
    public int maxLevelSum(TreeNode root) {
        // 返回层内元素之和最大的层号，且是最小的层号

        // 广度优先遍历，一层一层向下，遇到最大值就记录层号（深度），返回最大值的层号，因为是从上向下遍历，如果没有更大值，那么当前的最大值就是最小层

        // 队列，保存每一层的节点，队列是动态的，只保存一层的节点
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        // 树的深度、初始最大值、最大值的深度
        int dept = 0;
        int max = root.val;
        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);
        }
    }
}