口碑好的企业网站建设,seo短视频网页,软件设计工作室网站,免费店铺logo目录链接#xff1a;
力扣编程题-解法汇总_分享记录-CSDN博客 GitHub同步刷题项目#xff1a;
https://github.com/September26/java-algorithms 原题链接#xff1a;. - 力扣#xff08;LeetCode#xff09; 描述#xff1a;
给你一棵二叉树的根节点 root 和一个正整… 目录链接
力扣编程题-解法汇总_分享记录-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 。提示
树中的节点数为 n2 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){vectorlong long levelSum;searchTreeNode(levelSum, root, 0);sort(levelSum.begin(), levelSum.end());if (static_castint(levelSum.size()) - k 0){return -1;}return levelSum[levelSum.size() - k];}void searchTreeNode(vectorlong 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(vectorlong long levelSum, int level, int value){if (level levelSum.size()){levelSum.push_back(value);}else{levelSum[level] value;}}
};
