Leetcode Weekly 419
B
C++
https://telegram.me/+_hn3cBQVbGliYTI9
class Solution {
public:
pair checkPerfect(TreeNode* node) {
if (!node) return {true, 0};
auto leftResult = checkPerfect(node->left);
auto rightResult = checkPerfect(node->right);
if (leftResult.first && rightResult.first && leftResult.second == rightResult.second) {
return {true, leftResult.second + rightResult.second + 1};
}
return {false, 0};
}
void gatherPerfectSizes(TreeNode* node, vector& subtreeSizes) {
if (!node) return;
auto result = checkPerfect(node);
if (result.first) {
subtreeSizes.push_back(result.second);
}
gatherPerfectSizes(node->left, subtreeSizes);
gatherPerfectSizes(node->right, subtreeSizes);
}
int kthLargestPerfectSubtree(TreeNode* root, int k) {
vector subtreeSizes;
gatherPerfectSizes(root, subtreeSizes);
if (subtreeSizes.empty()) return -1;
sort(subtreeSizes.rbegin(), subtreeSizes.rend());
return (k
B
C++
https://telegram.me/+_hn3cBQVbGliYTI9
class Solution {
public:
pair checkPerfect(TreeNode* node) {
if (!node) return {true, 0};
auto leftResult = checkPerfect(node->left);
auto rightResult = checkPerfect(node->right);
if (leftResult.first && rightResult.first && leftResult.second == rightResult.second) {
return {true, leftResult.second + rightResult.second + 1};
}
return {false, 0};
}
void gatherPerfectSizes(TreeNode* node, vector& subtreeSizes) {
if (!node) return;
auto result = checkPerfect(node);
if (result.first) {
subtreeSizes.push_back(result.second);
}
gatherPerfectSizes(node->left, subtreeSizes);
gatherPerfectSizes(node->right, subtreeSizes);
}
int kthLargestPerfectSubtree(TreeNode* root, int k) {
vector subtreeSizes;
gatherPerfectSizes(root, subtreeSizes);
if (subtreeSizes.empty()) return -1;
sort(subtreeSizes.rbegin(), subtreeSizes.rend());
return (k