https://leetcode.com/problems/kth-largest-sum-in-a-binary-tree
2583.Kth Largest Sum in a Binary Tree
给一个二元树 root 跟正整数 k
level sum 是同一层的 node 加总
回传第k个大的level sum 如果k超过level则回传-1
Example 1:
https://assets.leetcode.com/uploads/2022/12/14/binaryytreeedrawio-2.png
Input: root = [5,8,9,2,1,3,7,4,6], k = 2
Output: 13
Explanation: 各个level的总和如下
- Level 1: 5
- Level 2: 8 + 9 = 17
- Level 3: 2 + 1 + 3 + 7 = 13
- Level 4: 4 + 6 = 10
第2大的为 13
Example 2:
https://assets.leetcode.com/uploads/2022/12/14/treedrawio-3.png
Input: root = [1,2,null,3], k = 1
Output: 3
Explanation: 最大的为 3
Constraints:
* 树的节点数为 n
* 2 <= n <= 10^5
* 1 <= Node.val <= 10^6
* 1 <= k <= n
思路：
有左或右就接着算并把level+1
记得要判断层数是否比k小
最后排序回传第k个大的值
Python Code:
# 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 = right
from collections import defaultdict
class Solution:
def kthLargestLevelSum(self, root, OptionalpTreeNode], k: int) -> int:
level = 1
res = defaultdict(int)
def c(i: TreeNode, res: defaultdict, level: int):
if i.left:
c(i.left, res, level+1)
if i.right:
c(i.right, res, level+1)
res[level] += i.val
c(root, res, level)
if len(res.values()) < k: return -1
return sorted(res.values(), reverse=True)[k-1]
终于有一题TreeNode会 我要哭了