Medium

题目描述

给你一个二叉树的根节点 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, 10^4] 范围内
  • -10^5 <= Node.val <= 10^5

解题思路

这道题要求找出二叉树中层内元素和最大的层数，可以用层序遍历（BFS）或深度优先搜索（DFS）来解决。

解法一：层序遍历（BFS） - 推荐解法

使用广度优先搜索按层遍历二叉树，逐层计算每层元素的和。使用队列来维护当前层的所有节点，每次处理完一层后，记录该层的和，并将下一层的节点入队。

这种方法的优势是思路清晰，直接按层处理，容易理解和实现。

解法二：深度优先搜索（DFS）

使用 DFS 遍历二叉树，同时传递当前节点的层数。使用一个数组或哈希表来记录每一层的元素和，最后找出和最大的层。

两种方法的时间复杂度都是 O(n)，空间复杂度在最坏情况下都是 O(n)。BFS 方法更直观，因为它天然按层处理数据，而 DFS 需要额外的数据结构来记录每层信息。

最终遍历完所有层后，找出元素和最大的层，如果有多个层的和相等且都是最大值，返回最小的层数。

代码实现

class Solution {
public:
    int maxLevelSum(TreeNode* root) {
        if (!root) return 1;
        
        queue<TreeNode*> q;
        q.push(root);
        int level = 1, maxSum = root->val, result = 1;
        
        while (!q.empty()) {
            int size = q.size();
            int currentSum = 0;
            
            for (int i = 0; i < size; i++) {
                TreeNode* node = q.front();
                q.pop();
                currentSum += node->val;
                
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
            
            if (currentSum > maxSum) {
                maxSum = currentSum;
                result = level;
            }
            level++;
        }
        
        return result;
    }
};

class Solution:
    def maxLevelSum(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 1
        
        queue = [root]
        level = 1
        max_sum = root.val
        result = 1
        
        while queue:
            size = len(queue)
            current_sum = 0
            
            for _ in range(size):
                node = queue.pop(0)
                current_sum += node.val
                
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            
            if current_sum > max_sum:
                max_sum = current_sum
                result = level
            
            level += 1
        
        return result

public class Solution {
    public int MaxLevelSum(TreeNode root) {
        if (root == null) return 1;
        
        Queue<TreeNode> queue = new Queue<TreeNode>();
        queue.Enqueue(root);
        int level = 1, maxSum = root.val, result = 1;
        
        while (queue.Count > 0) {
            int size = queue.Count;
            int currentSum = 0;
            
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.Dequeue();
                currentSum += node.val;
                
                if (node.left != null) queue.Enqueue(node.left);
                if (node.right != null) queue.Enqueue(node.right);
            }
            
            if (currentSum > maxSum) {
                maxSum = currentSum;
                result = level;
            }
            level++;
        }
        
        return result;
    }
}

var maxLevelSum = function(root) {
    if (!root) return 1;
    
    let queue = [root];
    let level = 1, maxSum = root.val, result = 1;
    
    while (queue.length > 0) {
        let size = queue.length;
        let currentSum = 0;
        
        for (let i = 0; i < size; i++) {
            let node = queue.shift();
            currentSum += node.val;
            
            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
        }
        
        if (currentSum > maxSum) {
            maxSum = currentSum;
            result = level;
        }
        level++;
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型BFS解法DFS解法
时间复杂度O(n)O(n)
空间复杂度O(w)O(h + l)

其中：

  • n 为二叉树节点总数
  • w 为二叉树最大宽度（最多节点的层的节点数）
  • h 为二叉树高度
  • l 为二叉树层数

说明：

  • 时间复杂度：两种方法都需要遍历所有节点一次
  • 空间复杂度：BFS 使用队列存储当前层节点，最坏情况下队列大小等于最宽层的节点数；DFS 使用递归栈和额外数组存储每层和

相关题目