题目描述

给定一个二叉树，该二叉树的根节点是root。对这个二叉树进行分层，根节点位于第1层，根节点的左子树和右子树在第2层。如下图所示：

请返回元素之和最大的那个层号，如果存在多个相等的层则返回最小的层号。

示例1:

输入：root = [1,2,5,7,0,null,null]

输出：2

解释：

第1层各元素之和为1

第2层各元素之和为7

第3层各元素之和为7

由于第2层和第3层相等，但是第2层更小，返回2；

解题思路

这道题使用BFS是比较标准的解决方案（这里我使用队列，java中不用自己来实现对列），核心思路如下：

参考上图：

1. 先定义一个队列，Deque deque = new ArrayDeque();
2. 将root放到队列中，deque.offer(root);
3. 执行循环，跳出条件deque为空，循环逻辑如下：
   1. 计算当前层中各个元素之和，由于只有一个元素，计算结果为1；
   2. 将root的左子树和右子树加入到队列中。
   3. 比较求出元素之和最大的那个层号
4. 直接返回结果。

代码实现

 
import org.example.TreeNode;
 
import java.util.ArrayDeque;
import java.util.Deque;
 
class Solution {
    public int maxLevelSum(TreeNode root) {
 
        // 1. 创建一个队列
        Deque deque = new ArrayDeque<>();
 
        // 2. 将root加入到对列中
        if (root != null) {
            deque.offer(root);
        }
 
        int max = Integer.MIN_VALUE;
        int level = 0;
 
        int countLevel = 1;
        // 3. 执行循环，退出条件对列为空
        while (!deque.isEmpty()) {
            int sz = deque.size();
            
            // 3.0 准备一个sum，用于计算每层元素和
            int sum = 0;
 
            for (int i = 0; i < sz; i++) {
                
                TreeNode node = deque.poll();
                // 3.1 计算每层元素和
                sum += node.val;
                
                // 3.2.1 将左子树加入到队列中
                if (node.left != null) {
                    deque.offer(node.left);
                }
                // 3.2.1 将右子树加入到队列中
                if (node.right != null) {
                    deque.offer(node.right);
                }
            }
 
            // 3.3. 比较获取元素和最大的层
            if (max < sum) {
                max = sum;
                level = countLevel;
            }
 
            countLevel++;
        }
 
        // 4. 直接返回结果
        return level;
    }
 
    public static void main(String[] args) {
        Solution solution = new Solution();
        TreeNode root = new TreeNode(1);
 
        root.left = new TreeNode(7);
        root.right = new TreeNode(0);
 
        root.left.left = new TreeNode(7);
        root.left.right = new TreeNode(-8);
 
        System.out.println(solution.maxLevelSum(root));
 
    }
}

树的代码实现：

package org.example;

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;

    public TreeNode() {
    }

    public TreeNode(int val) {
        this.val = val;
    }

    public TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

 

总结

这道题是一道标准的BFS题目，我借助队列来解决计算每一层元素总和；总体来说：需要掌握树的构造，树的广度优先搜索，队列的使用，最后是最大元素的获取；整体复杂度可控，是一个锻炼思路的基础题目。