ASMR LeetCode: Kth Largest Sum in a Binary Tree | Chill Coding

ITS ALMOST SPOOKY DAYY

[LeekCodeDev]

Source 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
class Solution:
def kthLargestLevelSum(self, root: Optional[TreeNode], k: int) -> int:
'''
To solve this problem, I'm first going to check if I have enough levels
for k, if not I can just return -1 immediately. If I do have enough levels,
I'm going to traverse through each node, and mark their levels, and depending
on their level, I'm going to use that as the index of a master array
and increment the total at that index. This way, I can keep track of total
sums for each level, and at the end I can simply return the kth largest
by sorting the array with the biggest coming first :D
'''
def checkLevels(root):
if not root:
return 0
return 1 + max(checkLevels(root.left), checkLevels(root.right))
arr = [0] *
levels = checkLevels(root)
if levels < k:
return -1
def traverse(root, level):
if not root:
return 0
arr[level] += root.val
traverse(root.left, level+1)
traverse(root.right, level+1)

traverse(root, 0)
return sorted(arr, reverse=True)[k-1]