【LeetCode】最大层内元素和 Java 题解

作者：Albert

2022 年 8 月 05 日
本文字数：1500 字
阅读完需：约 5 分钟

题目描述

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

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

复制代码

思路分析

今天的算法题目是二叉树的题目，题目要求请返回层内元素之和最大的那几层（可能只有一层）的层号，并返回其中最小的那个。
分析题目之后，我们首先需要求出每一层的元素只和。求每次元素只和的时候，我们一般使用 BFS。BFS 全称是 Breadth First Search，中文名是宽度优先搜索，也叫广度优先搜索,是图上最基础、最重要的搜索算法之一。所谓宽度优先。就是每次都尝试访问同一层的节点。如果同一层都访问完了，再访问下一层。
在 Java 中，我们使用队列 Queue 来存储元素，完成 BFS 相关的功能，首先把 root 放入队列，然后每次计算出当前队列的长度，就是当前层元素的个数，逐个出队，完成当前层元素求和计算。
在求答案的过程中，我们定义了 ansNode 节点，记录当前的层数和最值，动态更新结果对象。
具体实现代码如下，请参考。

通过代码

/** * 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) {        AnsNode ans = new AnsNode(0, Integer.MIN_VALUE);        int maxSum = Integer.MIN_VALUE;        Queue<TreeNode> queue = new LinkedList<>();        queue.offer(root);        int currentLevel = 0;        while (!queue.isEmpty()) {            int size = queue.size();            int tempSum = 0;            currentLevel++;            for (int i = 0; i < size; i++) {                TreeNode node = queue.poll();                tempSum += node.val;                if (node.left != null) {                    queue.offer(node.left);                }                if (node.right != null) {                    queue.offer(node.right);                }            }
            if (tempSum > maxSum) {                maxSum = tempSum;                if (maxSum > ans.sum) {                    ans.sum = maxSum;                    ans.level = currentLevel;                }            }        }
        return ans.level;    }}
class AnsNode {    int level;    int sum;    AnsNode(int level, int sum) {        this.level = level;        this.sum = sum;    }}