Step By Step Solution
Intuition\n Describe your first thoughts on how to solve this problem. \n\nThe problem aims to identify the k-th largest subtree that is "perfect." A perfect su
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\nThe problem aims to identify the `k`-th largest subtree that is "perfect." A perfect subtree in a binary tree is one where all levels are fully filled. By exploring each subtree, we can check if it meets this criterion. If it does, we add its node count to a priority queue, which helps us track the largest subtree sizes. The `k`-th largest perfect subtree can then be retrieved by removing elements from the priority queue until we reach the desired count.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\nRecursive DFS Traversal:\n\nWe perform a depth-first search (DFS) traversal starting from the root. Each node returns the size of its subtree, and we maintain a `isPerfect` map to determine if a subtree rooted at a particular node (identified uniquely with the node value and index) is perfect.\nIdentifying Perfect Subtrees:\n\nFor each node, we check if both left and right subtrees are perfect, have equal size, and exist (both must be present). If these conditions are met, then the current subtree is also perfect.\nIf a subtree is perfect, we store its size in the priority queue pq and mark it as perfect in `isPerfect`.\nTracking Largest Sizes:\n\nAs we backtrack, for each perfect subtree, we push its size to the priority queue. This queue will automatically keep the sizes sorted in descending order.\nRetrieve `k`-th Largest Perfect Subtree:\n\nFinally, we pop elements from the priority queue `k` times to get the `k`-th largest perfect subtree size. If there are fewer than `k` perfect subtrees, we return -1.\n\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n`O(N)`, where `N` is the number of nodes in the tree. Each node is visited once in the DFS traversal, and priority queue operations are bounded by `O(logN)` which is manageable within this traversal.\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n`O(N)`, for storing `isPerfect` and priority queue operations. The recursive call stack also requires `O(N)` space.\n\n\n# Step-by-step\n\nLet\u2019s break down the process with diagrams, showing each subtree\u2019s state as we calculate whether it\'s perfect and then add it to the priority queue. Here\u2019s the tree we\u2019ll use as a reference:\n\n```markdown []\n          1\n        /   \\\n       2     3\n      / \\   / \\\n     4   5 6   7\n```\n\nStep-by-Step DFS with Diagrams\n\n1. Starting from Node 4\n    - Node `4` is a leaf node, so it\u2019s automatically a perfect subtree of size 1.\n    - We add `1` to the priority queue.\n    \n```makefile []\nPQ: [1]\n```\n\n2. Moving to Node 5\n    - Node `5` is also a leaf node, so it is also a perfect subtree of size 1.\n    - We add another `1` to the priority queue.\n\n```makefile []\nPQ: [1, 1]\n```\n\n3. Evaluating Node 2 (Subtree rooted at 2)\n    - Node `2` has two children, `4` and `5`, both of which are perfect subtrees of size `1` each.\n    - Since both subtrees are of equal size and are perfect, the subtree rooted at `2` is also perfect with a total size of `3` (1 + 1 + 1).\n    - We add `3` to the priority queue.\n\n```less []\n       2\n      / \\\n     4   5\n\nPQ: [3, 1, 1]\n```\n\n4. Moving to Node 6\n    - Node `6` is a leaf node, so it\u2019s a perfect subtree of size `1`.\n    - We add `1` to the priority queue.\n\n```makefile []\nPQ: [3, 1, 1, 1]\n```\n\n5. Moving to Node 7\n    - Node 7 is also a leaf node, so it\u2019s a perfect subtree of size 1.\n    - We add another 1 to the priority queue.\n\n\n```makefile []\nPQ: [3, 1, 1, 1, 1]\n```\n\n6. Evaluating Node 3 (Subtree rooted at 3)\n    - Node `3` has two children, `6` and `7`, both of which are perfect subtrees of size `1`.\n    - Since both subtrees are of equal size and are perfect, the subtree rooted at `3` is also perfect with a total size of `3` (1 + 1 + 1).\n    - We add `3` to the priority queue.\n\n```less []\n       3\n      / \\\n     6   7\n\nPQ: [3, 3, 1, 1, 1, 1]\n```\n\n7. Evaluating Node 1 (Subtree rooted at 1)\n    - Node `1` has two children, `2` and `3`, both of which are perfect subtrees of size `3`.\n    - Since both subtrees are of equal size and are perfect, the entire tree rooted at `1` is also perfect with a total size of `7` (3 + 3 + 1).\n    - We add `7` to the priority queue.\n\n```less []\n       1\n     /   \\\n    2     3\n   / \\   / \\\n  4   5 6   7\n\nPQ: [7, 3, 3, 1, 1, 1, 1]\n```\n\n##### Retrieving the k-th Largest Perfect Subtree\nLet\'s say we want the 2nd largest perfect subtree (`k = 2`):\n\nPop the priority queue to get the largest element (`7`).\nPop again to get the next largest element (`3`).\nThe 2nd largest perfect subtree has a size of `3`.\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, unordered_map<string, bool>& isPerfect, priority_queue<int>& pq, int idx) {\n        if(root == NULL) return 0;\n        if(root->left == NULL && root->right == NULL) {\n            isPerfect[to_string(root->val) + to_string(idx)] = true;\n            pq.push(1);\n            return 1;\n        }\n        int left = dfs(root->left, isPerfect, pq, (2*idx) + 1);\n        int right = dfs(root->right, isPerfect, pq, (2*idx) + 2);\n        if(root->left && root->right && isPerfect[to_string(root->left->val) + to_string((2*idx) + 1)] && isPerfect[to_string(root->right->val) + to_string((2*idx) + 2)] && left == right) {\n            pq.push(left + right + 1);\n            isPerfect[to_string(root->val) + to_string(idx)] = true;\n        }\n        return left + right + 1;\n    }\n\n    int kthLargestPerfectSubtree(TreeNode* root, int k) {\n        unordered_map<string, bool> isPerfect;\n        priority_queue<int> pq;\n        dfs(root, isPerfect, pq, 0);\n        int res = -1;\n        while(!pq.empty() && k > 0) {\n            res = pq.top();\n            pq.pop();\n            k--;\n        }\n        return k > 0 ? -1 : res;\n    }\n};\n```
['C++']