LeetCode 2583.二叉树中的第 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 。

提示：

• 树中的节点数为 n
• 2 public: ll kthLargestLevelSum(TreeNode* root, int k) { vector 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, val=0, left=None, right=None):#         self.val = val#         self.left = left#         self.right = rightclass Solution:    def kthLargestLevelSum(self, root: TreeNode, k: int) -> int:        values = []        q = [root]        while q:            cnt = 0            thisLayer = q            q = []            for thisNode in thisLayer:                cnt += thisNode.val                if 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和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

  Tisfy：https://letmefly.blog.csdn.net/article/details/136252010