Medium

题目描述

给你一个二叉树的根节点 root 和一个整数 k。

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

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

示例 1：

输入：root = [5,3,6,5,2,5,7,1,8,null,null,6,8], k = 2
输出：3
解释：
完美二叉子树的根节点用黑色标出。它们的大小按非递增顺序为 [3, 3, 1, 1, 1, 1, 1, 1]。
第 2 大的大小是 3。

示例 2：

输入：root = [1,2,3,4,5,6,7], k = 1
输出：7
解释：
完美二叉子树的大小按非递增顺序为 [7, 3, 3, 1, 1, 1, 1]。最大完美二叉子树的大小是 7。

示例 3：

输入：root = [1,2,3,null,4], k = 3
输出：-1
解释：
完美二叉子树的大小按非递增顺序为 [1, 1]。没有第 3 大的完美二叉子树。

提示：

  • 树中节点数目的范围是 [1, 2000]
  • 1 <= Node.val <= 2000
  • 1 <= k <= 1024

解题思路

解题思路

这道题需要找到二叉树中所有完美子树的大小，然后返回第 k 大的值。

核心思路：

  1. 递归判断完美子树：对于每个节点，我们需要判断以它为根的子树是否为完美二叉树

  2. 完美二叉树的特征：

    • 空树是完美的（大小为0）
    • 叶子节点是完美的（大小为1）
    • 非叶子节点要完美，需要左右子树都完美且高度相同

  3. DFS 遍历：使用深度优先搜索遍历所有节点，对每个节点检查其子树是否完美

  4. 收集结果：将所有完美子树的大小收集起来，排序后返回第 k 大的值

算法步骤：

  1. 定义递归函数，返回以当前节点为根的子树信息（是否完美、高度、大小）
  2. 对于每个节点：
    • 如果是空节点，返回完美（高度0，大小0）
    • 递归处理左右子树
    • 如果左右子树都完美且高度相同，当前子树也完美
    • 计算当前子树大小 = 左子树大小 + 右子树大小 + 1
  3. 收集所有完美子树的大小，排序后返回第 k 大的值

推荐解法： 使用 DFS + 排序的方法，时间复杂度合理且代码清晰。

代码实现

class Solution {
public:
    vector<int> perfectSizes;
    
    // 返回 {是否完美, 高度, 大小}
    tuple<bool, int, int> dfs(TreeNode* node) {
        if (!node) return {true, 0, 0};
        
        auto [leftPerfect, leftHeight, leftSize] = dfs(node->left);
        auto [rightPerfect, rightHeight, rightSize] = dfs(node->right);
        
        bool isPerfect = leftPerfect && rightPerfect && leftHeight == rightHeight;
        int height = max(leftHeight, rightHeight) + 1;
        int size = leftSize + rightSize + 1;
        
        if (isPerfect) {
            perfectSizes.push_back(size);
        }
        
        return {isPerfect, height, size};
    }
    
    int kthLargestPerfectSubtree(TreeNode* root, int k) {
        perfectSizes.clear();
        dfs(root);
        
        sort(perfectSizes.rbegin(), perfectSizes.rend());
        
        return k <= perfectSizes.size() ? perfectSizes[k-1] : -1;
    }
};

class Solution:
    def kthLargestPerfectSubtree(self, root: Optional[TreeNode], k: int) -> int:
        perfect_sizes = []
        
        def dfs(node):
            if not node:
                return True, 0, 0  # 是否完美, 高度, 大小
            
            left_perfect, left_height, left_size = dfs(node.left)
            right_perfect, right_height, right_size = dfs(node.right)
            
            is_perfect = left_perfect and right_perfect and left_height == right_height
            height = max(left_height, right_height) + 1
            size = left_size + right_size + 1
            
            if is_perfect:
                perfect_sizes.append(size)
            
            return is_perfect, height, size
        
        dfs(root)
        perfect_sizes.sort(reverse=True)
        
        return perfect_sizes[k-1] if k <= len(perfect_sizes) else -1

public class Solution {
    private List<int> perfectSizes = new List<int>();
    
    private (bool isPerfect, int height, int size) Dfs(TreeNode node) {
        if (node == null) return (true, 0, 0);
        
        var left = Dfs(node.left);
        var right = Dfs(node.right);
        
        bool isPerfect = left.isPerfect && right.isPerfect && left.height == right.height;
        int height = Math.Max(left.height, right.height) + 1;
        int size = left.size + right.size + 1;
        
        if (isPerfect) {
            perfectSizes.Add(size);
        }
        
        return (isPerfect, height, size);
    }
    
    public int KthLargestPerfectSubtree(TreeNode root, int k) {
        perfectSizes.Clear();
        Dfs(root);
        
        perfectSizes.Sort((a, b) => b.CompareTo(a));
        
        return k <= perfectSizes.Count ? perfectSizes[k-1] : -1;
    }
}

var kthLargestPerfectSubtree = function(root, k) {
    const sizes = [];
    
    function dfs(node) {
        if (!node) return [true, 0, 0]; // [isPerfect, size, height]
        
        if (!node.left && !node.right) {
            sizes.push(1);
            return [true, 1, 1];
        }
        
        const [leftPerfect, leftSize, leftHeight] = dfs(node.left);
        const [rightPerfect, rightSize, rightHeight] = dfs(node.right);
        
        if (leftPerfect && rightPerfect && leftHeight === rightHeight) {
            const size = leftSize + rightSize + 1;
            sizes.push(size);
            return [true, size, leftHeight + 1];
        }
        
        return [false, 0, 0];
    }
    
    dfs(root);
    sizes.sort((a, b) => b - a);
    
    return k <= sizes.length ? sizes[k - 1] : -1;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(n log n)其中 n 是树中节点数。DFS 遍历需要 O(n)，排序最多需要 O(n log n)
空间复杂度O(n)递归栈深度最多 O(n)，存储完美子树大小的数组最多 O(n)

相关题目