​LeetCode解法汇总2583. 二叉树中的第 K 大层和

本文主要是介绍​LeetCode解法汇总2583. 二叉树中的第 K 大层和，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

 目录链接：

力扣编程题-解法汇总_分享+记录-CSDN博客

GitHub同步刷题项目：

https://github.com/September26/java-algorithms

原题链接：. - 力扣（LeetCode）

描述：

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

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

返回树中第 k 大的层和（不一定不同）。如果树少于 k 层，则返回 -1 。

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

示例 1：

输入：root = [5,8,9,2,1,3,7,4,6], k = 2
输出：13
解释：树中每一层的层和分别是：
- Level 1: 5
- Level 2: 8 + 9 = 17
- Level 3: 2 + 1 + 3 + 7 = 13
- Level 4: 4 + 6 = 10
第 2 大的层和等于 13 。

示例 2：

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

提示：

• 树中的节点数为 n
• 2 <= n <= 105
• 1 <= Node.val <= 106
• 1 <= k <= n

解题思路：

构建一个数组，存放每个层级的值之和。

使用searchTreeNode方法进行深度搜索，传入参数为当前节点以及所在层级。

最后对层级数组进行排序，倒序取第k位即可。

代码：

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:long long kthLargestLevelSum(TreeNode *root, int k){vector<long long> levelSum;searchTreeNode(levelSum, root, 0);sort(levelSum.begin(), levelSum.end());if (static_cast<int>(levelSum.size()) - k < 0){return -1;}return levelSum[levelSum.size() - k];}void searchTreeNode(vector<long long> &levelSum, TreeNode *root, int level){if (root == nullptr){return;}addLevelValue(levelSum, level, root->val);searchTreeNode(levelSum, root->left, level + 1);searchTreeNode(levelSum, root->right, level + 1);}void addLevelValue(vector<long long> &levelSum, int level, int value){if (level == levelSum.size()){levelSum.push_back(value);}else{levelSum[level] += value;}}
};

这篇关于​LeetCode解法汇总2583. 二叉树中的第 K 大层和的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---