diff options
author | Jack Sangdahl <[email protected]> | 2024-10-21 19:28:33 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2024-10-21 19:28:33 -0600 |
commit | 79945065d30539dc039f0e77cf8c9fc0058ec2c7 (patch) | |
tree | 4ba9046bc28dc24fc1a82aa2262a724a52be1e9a /kth_largest_sum_binary_tree.py | |
parent | 3f53cedfddf11641d652d347b25df64807a4468a (diff) | |
download | leetcode-79945065d30539dc039f0e77cf8c9fc0058ec2c7.tar.gz leetcode-79945065d30539dc039f0e77cf8c9fc0058ec2c7.zip |
2583. kth largest sum in a binary tree
Diffstat (limited to 'kth_largest_sum_binary_tree.py')
-rw-r--r-- | kth_largest_sum_binary_tree.py | 45 |
1 files changed, 45 insertions, 0 deletions
diff --git a/kth_largest_sum_binary_tree.py b/kth_largest_sum_binary_tree.py new file mode 100644 index 0000000..8f853ba --- /dev/null +++ b/kth_largest_sum_binary_tree.py @@ -0,0 +1,45 @@ +# 2583. Kth Largest Sum in a Binary Tree + +""" +you are given the 'root' of a binary tree and a positive integer 'k'. the +level sum in the tree is the sum of the values of the nodes that are on the +same level. return the k'th largest level sum in the tree (not necessarily +distinct). if there are fewer than 'k' levels in the tree, return -1. note +that two nodes are on the same level if they have the same distance from the +root. +""" + + +# Definition for a binary tree node. +class TreeNode(object): + def __init__(self, val=0, left=None, right=None): + self.val = val + self.left = left + self.right = right + + +class Solution(object): + def kthLargestLevelSum(self, root, k): + """ + :type root: Optional[TreeNode] + :type k: int + :rtype: int + """ + vals = [] + stack = [(root, 0)] + while stack: + node, i = stack.pop() + if i == len(vals): + vals.append(0) + vals[i] += node.val + if node.left: + stack.append((node.left, i + 1)) + if node.right: + stack.append((node.right, i + 1)) + return sorted(vals, reverse=True)[k - 1] if len(vals) >= k else -1 + + +if __name__ == "__main__": + obj = Solution() + print(obj.kthLargestLevelSum(root=[5, 8, 9, 2, 1, 3, 7, 4, 6], k=2)) + print(obj.kthLargestLevelSum(root=[1, 2, None, 3])) |