烟台网站关键词推广,找房网58同城买房,什么类型的网站流量高,正规的常州网站推广【LetMeFly】2583.二叉树中的第 K 大层和#xff1a;层序遍历 排序
力扣题目链接#xff1a;https://leetcode.cn/problems/kth-largest-sum-in-a-binary-tree/
给你一棵二叉树的根节点 root 和一个正整数 k 。
树中的 层和 是指 同一层 上节点值的总和。
返回树中第 k …【LetMeFly】2583.二叉树中的第 K 大层和层序遍历 排序
力扣题目链接https://leetcode.cn/problems/kth-largest-sum-in-a-binary-tree/
给你一棵二叉树的根节点 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
方法一层序遍历 排序
如果已经掌握了二叉树的层序遍历那么这道题将会如鱼得水。
我们依然进行层序遍历在层序遍历的过程中计算每一层的节点值之和并加入到一个数组中。
遍历结束后对数组进行排序返回第k大值或-1即可。
时间复杂度 O ( N 1 N 2 log N 2 ) O(N1 N2\log N2) O(N1N2logN2)其中 N 1 N1 N1是二叉树节点个数 N 2 N2 N2是二叉树深度空间复杂度 O ( N 3 N 2 ) O(N3 N2) O(N3N2)其中 N 3 N3 N3是最多一层的节点个数
时空复杂度也可以将全部的 N N N都视为二叉树节点个数。
AC代码
C
typedef long long ll;
class Solution {
public:ll kthLargestLevelSum(TreeNode* root, int k) {vectorll values;queueTreeNode* q;q.push(root);while (q.size()) {ll cnt 0;for (int _ q.size(); _ 0; _--) {TreeNode* thisNode q.front();q.pop();cnt thisNode-val;if (thisNode-left) {q.push(thisNode-left);}if (thisNode-right) {q.push(thisNode-right);}}values.push_back(cnt);}sort(values.begin(), values.end());return k values.size() ? -1 : values[values.size() - k];}
};Python
注意本题数据级别是 1 0 5 10^5 105不能使用数组切片模拟队列的方式。
# # Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val0, leftNone, rightNone):
# self.val val
# self.left left
# self.right rightclass Solution:def kthLargestLevelSum(self, root: TreeNode, k: int) - int:values []q [root]while q:cnt 0thisLayer qq []for thisNode in thisLayer:cnt thisNode.valif thisNode.left:q.append(thisNode.left)if thisNode.right:q.append(thisNode.right)values.append(cnt)values.sort()return values[len(values) - k] if len(values) k else -1同步发文于CSDN和我的个人博客原创不易转载经作者同意后请附上原文链接哦~ Tisfyhttps://letmefly.blog.csdn.net/article/details/136252010
