Straightforward O(n log k) Easy Approach with Intuition
Intuition\nThe key to solving this problem is to trust your recursive approach to return the correct result without needing to implement every detail upfront. S
# Intuition\nThe key to solving this problem is to trust your recursive approach to return the correct result without needing to implement every detail upfront. Specifically, we assume the recursion will return the size of the perfect subtree or `-1` if it\u2019s not possible for a subtree to be perfect. Additionally, null nodes are considered perfect subtrees of size 0, which simplifies the recursion. All these makes it easier to handle the recursive cases, especially for combining results from the left and right subtrees.\n\n# Approach\n1. Perform a DFS traversal starting from the root.\n2. For each node, use recursion to calculate the sizes of the left and right subtrees. If both subtrees are perfect (including null nodes as perfect subtrees of size 0) and their sizes are equal, the current node forms a larger perfect subtree.\n3. Store the sizes of all valid perfect subtrees in a priority queue (min-heap) and maintain the K largest subtree sizes. If the number of subtrees found is less than K, return `-1`.\n4. By limiting the size of the priority queue to K, we can efficiently retrieve the K-th largest perfect subtree size.\n\n# Complexity\n- **Time complexity:**  \n  The DFS traversal itself takes $$O(n)$$ where $$n$$ is the number of nodes in the tree. For every perfect subtree size that we find, we insert it into a priority queue (min-heap) of size at most K. Inserting into a heap takes $$O(\\log k)$$, which is much better than $$O(\\log n)$$ if $$k < n$$. Therefore, the overall time complexity is $$O(n \\log k)$$, which is more efficient than $$O(n \\log n)$$.\n\n- **Space complexity:**  \n  The space complexity is $$O(k)$$ for the priority queue and $$O(h)$$ for the recursion stack, where $$h$$ is the height of the tree. In the worst case, $$h = O(n)$$ for a skewed tree, so the total space complexity is $$O(k + h)$$.\n\n# Code\n```cpp\n/**\n * Definition for a binary tree node.\n * struct TreeNode {\n *     int val;\n *     TreeNode *left;\n *     TreeNode *right;\n *     TreeNode() : val(0), left(nullptr), right(nullptr) {}\n *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}\n *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}\n * };\n */\nclass Solution {\npublic:\n    priority_queue<int, vector<int>, greater<int>> pq;\n\n    int dfs(TreeNode* root, int k) {\n        if (!root) return 0;  // Null nodes are considered perfect subtrees of size 0\n        int x = dfs(root->left, k), y = dfs(root->right, k);\n        // If either subtree is not perfect, or their sizes are different\n        if (x == -1 || y == -1 || x != y)\n            return -1;\n        pq.push(1 + x + y);\n        // Maintain a min-heap of size K\n        while (pq.size() > k) pq.pop();\n        return 1 + x + y;\n    }\n\n    int kthLargestPerfectSubtree(TreeNode* root, int k) {\n        dfs(root, k);\n        // If we have fewer than K perfect subtrees, return -1\n        if (pq.size() < k) return -1;\n        return pq.top();\n    }\n};\n```
['C++']