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會 我要哭了