🚀 Optimized DFS-Based Solution for K-th Largest Perfect Subtree in Binary Tree
Intuition\nThe problem requires identifying perfect binary subtrees within a given binary tree. A perfect binary subtree has all its leaves at the same level, a
# Intuition\nThe problem requires identifying perfect binary subtrees within a given binary tree. A perfect binary subtree has all its leaves at the same level, and every parent has exactly two children. The key observation is that the size of a perfect binary subtree can be computed recursively if both the left and right subtrees are perfect and of equal size.\n\n# Approach\n1. Use a recursive depth-first search (DFS) to traverse the tree.\n2. For each node, calculate the sizes of its left and right subtrees.\n   - If both left and right subtrees are perfect and of equal size, the current subtree is also a perfect binary subtree. The size of this subtree is \\(1 + \\text{left size} + \\text{right size}\\).\n   - Otherwise, the current subtree is not perfect.\n3. Store the sizes of all perfect binary subtrees in a list.\n4. After traversing the tree, find the k-th largest size:\n   - If the size list has fewer than \\(k\\) elements, return \\(-1\\).\n   - Otherwise, use an efficient selection algorithm (`nth_element`) to determine the k-th largest size.\n\n\n\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    int dfs(TreeNode* root,vector<int> &ans){\n        if(!root) return 0;\n        int l=dfs(root->left,ans);\n        int r=dfs(root->right,ans);\n        if(l!=-1 && r!=-1 && l==r) ans.push_back(1+l+r);\n        else return -1;\n        return 1+l+r;\n    }\n    int kthLargestPerfectSubtree(TreeNode* root, int k) {\n        vector<int>ans;\n        dfs(root,ans);\n        sort(ans.begin(),ans.end(),greater<int>());\n\n        if(ans.size()>=k){\n            return ans[k-1];\n        }\n        return -1;\n    }\n};\n```
['Tree', 'Depth-First Search', 'Sorting', 'Binary Tree', 'C++']