Medium

题目描述

给你一个二叉树的根节点 root 和一个正整数 k。

树中的层和是指在同一层上节点值的总和。

返回树中第 k 大的层和（不需要去重）。如果树的层数小于 k，返回 -1。

注意，如果两个节点与根节点的距离相同，则它们在同一层。

示例 1：

输入：root = [5,8,9,2,1,3,7,4,6], k = 2
输出：13
解释：层和如下：
- 第 1 层：5。
- 第 2 层：8 + 9 = 17。
- 第 3 层：2 + 1 + 3 + 7 = 13。
- 第 4 层：4 + 6 = 10。
第2大的层和是13。

示例 2：

输入：root = [1,2,null,3], k = 1
输出：3
解释：最大的层和是3。

约束条件：

  • 树中节点的数目为 n
  • 2 <= n <= 10^5
  • 1 <= Node.val <= 10^6
  • 1 <= k <= n

解题思路

这道题需要计算二叉树每层的节点和，然后找到第K大的层和。

核心思路：

  1. 层序遍历计算层和：使用BFS（广度优先搜索）逐层遍历二叉树，计算每一层的节点值总和。我们可以用队列来实现层序遍历，每次处理完一层的所有节点后，将它们的子节点加入队列。

  2. 排序找第K大：将所有层和存储在数组中，然后对数组进行降序排序，返回第K个元素（索引为k-1）。

  3. 边界情况处理：如果树的层数少于k层，返回-1。

实现细节：

  • 使用队列进行BFS遍历，每次记录当前层的节点数量
  • 对于每一层，计算所有节点值的总和
  • 将层和存入数组，最后排序取第k大值

时间复杂度主要来自BFS遍历和排序，空间复杂度主要是队列和层和数组的存储。

代码实现

class Solution {
public:
    long long kthLargestLevelSum(TreeNode* root, int k) {
        vector<long long> levelSums;
        queue<TreeNode*> q;
        q.push(root);
        
        while (!q.empty()) {
            int levelSize = q.size();
            long long levelSum = 0;
            
            for (int i = 0; i < levelSize; i++) {
                TreeNode* node = q.front();
                q.pop();
                levelSum += node->val;
                
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
            
            levelSums.push_back(levelSum);
        }
        
        if (levelSums.size() < k) return -1;
        
        sort(levelSums.begin(), levelSums.end(), greater<long long>());
        return levelSums[k - 1];
    }
};

class Solution:
    def kthLargestLevelSum(self, root: Optional[TreeNode], k: int) -> int:
        level_sums = []
        queue = [root]
        
        while queue:
            level_size = len(queue)
            level_sum = 0
            next_queue = []
            
            for _ in range(level_size):
                node = queue.pop(0)
                level_sum += node.val
                
                if node.left:
                    next_queue.append(node.left)
                if node.right:
                    next_queue.append(node.right)
            
            level_sums.append(level_sum)
            queue = next_queue
        
        if len(level_sums) < k:
            return -1
        
        level_sums.sort(reverse=True)
        return level_sums[k - 1]

public class Solution {
    public long KthLargestLevelSum(TreeNode root, int k) {
        List<long> levelSums = new List<long>();
        Queue<TreeNode> queue = new Queue<TreeNode>();
        queue.Enqueue(root);
        
        while (queue.Count > 0) {
            int levelSize = queue.Count;
            long levelSum = 0;
            
            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.Dequeue();
                levelSum += node.val;
                
                if (node.left != null) queue.Enqueue(node.left);
                if (node.right != null) queue.Enqueue(node.right);
            }
            
            levelSums.Add(levelSum);
        }
        
        if (levelSums.Count < k) return -1;
        
        levelSums.Sort((a, b) => b.CompareTo(a));
        return levelSums[k - 1];
    }
}

var kthLargestLevelSum = function(root, k) {
    const levelSums = [];
    const queue = [root];
    
    while (queue.length > 0) {
        const levelSize = queue.length;
        let levelSum = 0;
        
        for (let i = 0; i < levelSize; i++) {
            const node = queue.shift();
            levelSum += node.val;
            
            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
        }
        
        levelSums.push(levelSum);
    }
    
    if (levelSums.length < k) return -1;
    
    levelSums.sort((a, b) => b - a);
    return levelSums[k - 1];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n + h log h)n为节点数（BFS遍历），h为树的高度（排序层和数组）
空间复杂度O(w + h)w为树的最大宽度（队列空间），h为树的高度（层和数组）

相关题目