[LeetCode] 2583. Kth Largest Sum in a Binary Tree

https://leetcode.com/problems/kth-largest-sum-in-a-binary-tree/description/?envType=daily-question&envId=2024-10-22

leetcode - Kth Largest Sum in a Binary Tree

문제 유형: BFS, 우선순위 큐

문제 난이도: Medium

 

문제

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 kth 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.

 

이진트리의 루트와 정수 k를 받습니다.

level sum은 같은 레벨의 노드들의 값의 합입니다.

k번째로 큰 level sum을 구하시오. 순위는 중복을 포함합니다.

 

풀이

BFS를 큐의 크기만큼 끊어서 하면, 레벨별로 구분하여 탐색할 수 있다.

레벨별로 구분하여 최대 힙 우선순위 큐에 넣어서 k번째로 꺼내지는 수가 요구되는 값이다.

 

코드

C++

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    long long kthLargestLevelSum(TreeNode* root, int k) {
        priority_queue<long long> pq;
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty()) {
            int qSize = q.size();
            long long sum = 0;
            for(int i = 0; i < qSize; ++i) {
                auto curr = q.front();
                q.pop();

                sum += curr -> val;
                if(curr -> left) q.push(curr -> left);
                if(curr -> right) q.push(curr -> right);
            }
            pq.push(sum);
        }

        for(int i = 0; i < k-1; ++i) {
            if(pq.empty()) return -1;
            pq.pop();
        }
        return pq.empty()? -1 : pq.top();
    }
};