3319. K-th Largest Perfect Subtree Size in Binary Tree

Posted on Edited on In

3319. K-th Largest Perfect Subtree Size in Binary Tree

Description

You are given the root of a binary tree and an integer k.

Return an integer denoting the size of the k^th largest perfect binary subtree, or -1 if it doesn’t exist.

A perfect binary tree is a tree where all leaves are on the same level, and every parent has two children.

Example 1:

1
2
3
Input: root = [5,3,6,5,2,5,7,1,8,null,null,6,8], k = 2

Output: 3

Explanation:

The roots of the perfect binary subtrees are highlighted in black. Their sizes, in non-increasing order are [3, 3, 1, 1, 1, 1, 1, 1].

The 2^nd largest size is 3.

Example 2:

1
2
3
Input: root = [1,2,3,4,5,6,7], k = 1

Output: 7

Explanation:

The sizes of the perfect binary subtrees in non-increasing order are [7, 3, 3, 1, 1, 1, 1]. The size of the largest perfect binary subtree is 7.

Example 3:

1
2
3
Input: root = [1,2,3,null,4], k = 3

Output: -1

Explanation:

The sizes of the perfect binary subtrees in non-increasing order are [1, 1]. There are fewer than 3 perfect binary subtrees.

Constraints:

  • The number of nodes in the tree is in the range [1, 2000].
  • 1 <= Node.val <= 2000
  • 1 <= k <= 1024

Hints/Notes

Solution

Language: C++

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
33
34
35
36
37
38
39
40
41
42
43
44
/**
 * 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:
    priority_queue<int> pq;

    int kthLargestPerfectSubtree(TreeNode* root, int k) {
        traverse(root);
        while (!pq.empty() && k > 0) {
            int val = pq.top();
            pq.pop();
            k--;
            if (k == 0) {
                return val;
            }
        }
        return -1;
    }

    int traverse(TreeNode* root) {
        if (!root) {
            return 0;
        }
        int left = traverse(root->left);
        int right = traverse(root->right);
        if (left == right) {
            int res = left + right + 1;
            pq.push(res);
            return res;
        } else {
            return -1;
        }
    }
};