LEETCODE 49场周赛 第K大完美二叉子树的大小

这个题目本身很直接，谨以此题来熟练一下二叉树的相关操作的使用，好久没写二叉树的代码了，不熟练了有点，题目如下：题目链接传送门在这里题目链接传送门
给你一棵 二叉树 的根节点 root 和一个整数k。

返回第 k 大的 完美二叉子树的大小，如果不存在则返回 -1。

完美二叉树 是指所有叶子节点都在同一层级的树，且每个父节点恰有两个子节点。

子树 是指树中的某一个节点及其所有后代形成的树。

分析：其实简单分析一下哈，这个完美二叉树就是我们的完全二叉树的定义嘛，所以我们只需要判定每个节点是否是完全二叉树，然后返回其高度h，就可以根据这个高度h得到其节点个数为（2 ^h - 1）,然后进行排序就好。

具体代码如下：（实现细节详见代码注释）

/*** 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://这个函数是去判断该子树是否是完全二叉树的，是的话就返回子树高度，否则返回-1int getHeight(TreeNode* root) {if (!root) return 0;int leftHeight = getHeight(root->left);int rightHeight = getHeight(root->right);if (leftHeight == -1 || rightHeight == -1 || leftHeight != rightHeight) {return -1; // 不是完美二叉树}return leftHeight + 1; // 是完美二叉树，高度加1}// 递归函数来计算完美二叉子树的大小，根据height返回 完全二叉树的高度int getPerfectSubtreeSize(TreeNode* root) {int height = getHeight(root);if (height == -1) {return 0; // 不是完美二叉树，大小为0}// 完美二叉树的节点总数为 2^height - 1return (1 << height) - 1;}// 主函数int kthLargestPerfectSubtree(TreeNode* root, int k) {vector<int> sizes;findPerfectSubtrees(root, sizes);// 对所有完美二叉子树的大小进行排序sort(sizes.rbegin(), sizes.rend());// 返回第 k 大的完美二叉子树的大小return (k <= sizes.size()) ? sizes[k - 1] : -1;}private:// 辅助函数，递归查找所有完美二叉子树，遍历整个二叉树，采用的是前序遍历，把所有合法节点的节点数目保存到sizes数组里面void findPerfectSubtrees(TreeNode* root, vector<int>& sizes) {if (!root) return;int size = getPerfectSubtreeSize(root);if (size > 0) {sizes.push_back(size);}// 继续递归查找左右子树findPerfectSubtrees(root->left, sizes);findPerfectSubtrees(root->right, sizes);}};