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 <= 1051 <= Node.val <= 1061 <= 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;}}
};