2583. Kth Largest Sum in a Binary Tree

, , 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
    public long kthLargestLevelSum(TreeNode root, int k) {
        Queue<Long> minHeap = new PriorityQueue<>(); // 最小堆，堆顶值最小

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            long levelSum = 0;
            for (int i = queue.size(); i > 0; i--) {
                TreeNode node = queue.poll();
                levelSum += node.val;

                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }

            if (minHeap.size() < k || levelSum > minHeap.peek()) { // 注意比较堆顶大小仅在堆内元素个数大于等于 k 个时进行
                minHeap.offer(levelSum);
                if (minHeap.size() > k) { // 注意此 if 不能去掉，因为堆内元素不足 k 个时只能放入而不能移除
                    minHeap.poll();
                }
            }
        }

        return minHeap.size() < k ? -1 : minHeap.peek(); // 注意题目要求：如果树少于 k 层，则返回 -1
    }
}

References

2583. Kth Largest Sum in a Binary Tree