NeetCode #428LC-2583MediumTrees
← Back to All Problems#428 · #2583 · Kth Largest Sum in a Binary Tree(二叉树中的第 K 大层和)
📌 Problem Statement & Constraints
You are given the root of a binary tree and a positive integer
k. Return the k-th largest level sum (the sum of node values at each level), or -1 if there are fewer than k levels. Constraints: the number of nodes is in [1, 10^5], 1 <= Node.val <= 10^6, 1 <= k <= 10^5.💡 Core Algorithmic Approaches
- A BFS with a frozen level size collects each level's sum.
- Then sort the sums descending and index the
k-th. - If
kexceeds the number of levels, return -1. - A min-heap of size
kavoids the full sort, but at these limits the sort is simpler.
💻 Benchmark Python3 Implementation
class Solution:
def kthLargestLevelSum(self, root: Optional[TreeNode], k: int) -> int:
from collections import deque
q = deque([root])
sums = []
while q:
n = len(q)
s = 0
for _ in range(n):
node = q.popleft()
s += node.val
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
sums.append(s) # one entry per level
if k > len(sums):
return -1
sums.sort(reverse=True)
return sums[k - 1]⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n + L log L) where L is the number of levels: the BFS is linear and the sort is over the levels.
💾 Space Complexity
O(w) for the widest level plus O(L) for the sums.
⚠️ Interview Pitfalls & Follow-ups
- Using
kas a 0-indexed position: the problem is 1-indexed, hencesums[k - 1]. - Forgetting the
k > Lcase: the answer is -1. - Summing the whole tree: the sums are per level.
- Using a DFS without tracking depth: the level grouping would be lost.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.