LeetCode 题解工作台
第 K 大的完美二叉子树的大小
给你一棵 二叉树 的根节点 root 和一个整数 k 。 返回第 k 大的 完美二叉 子树 的大小，如果不存在则返回 -1 。 完美二叉树 是指所有叶子节点都在同一层级的树，且每个父节点恰有两个子节点。 示例 1： 输入： root = [5,3,6,5,2,5,7,1,8,null,null,6,…
4
题型
5
代码语言
3
相关题
当前训练重点
中等 · 二分·树·traversal
答案摘要
我们定义一个函数 ，用于计算以当前节点为根节点的完美二叉子树的大小，用一个数组 记录所有完美二叉子树的大小。如果以当前节点为根节点的子树不是完美二叉子树，则返回 。 函数 的执行过程如下：
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 二分·树·traversal 题型思路
题目描述
给你一棵 二叉树 的根节点 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 <= 20001 <= k <= 1024
解题思路
方法一：DFS + 排序
我们定义一个函数 ，用于计算以当前节点为根节点的完美二叉子树的大小，用一个数组 记录所有完美二叉子树的大小。如果以当前节点为根节点的子树不是完美二叉子树，则返回 。
函数 的执行过程如下：
- 如果当前节点为空，则返回 ；
- 递归计算左子树和右子树的完美二叉子树的大小，分别记为 和 ；
- 如果左子树和右子树的大小不相等，或者左子树和右子树的大小小于 ，则返回 ；
- 计算当前节点的完美二叉子树的大小 ，并将 添加到数组 中；
- 返回 。
我们调用 函数计算出所有完美二叉子树的大小，如果数组 的长度小于 ，则返回 ，否则对数组 进行降序排序，返回第 大的完美二叉子树的大小。
时间复杂度 ，空间复杂度 。其中 是二叉树的节点数。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def kthLargestPerfectSubtree(self, root: Optional[TreeNode], k: int) -> int:
def dfs(root: Optional[TreeNode]) -> int:
if root is None:
return 0
l, r = dfs(root.left), dfs(root.right)
if l < 0 or l != r:
return -1
cnt = l + r + 1
nums.append(cnt)
return cnt
nums = []
dfs(root)
if len(nums) < k:
return -1
nums.sort(reverse=True)
return nums[k - 1]
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Look for a solution that emphasizes tree traversal and state management.
- question_mark
Expect the candidate to use DFS effectively to explore each subtree.
- question_mark
Check if the candidate handles edge cases like fewer perfect subtrees than k.
常见陷阱
外企场景- error
Failing to identify perfect subtrees correctly by not checking both children recursively.
- error
Inefficient sorting or traversal leading to higher than necessary time complexity.
- error
Missing the edge case where there are fewer than k perfect subtrees.
进阶变体
外企场景- arrow_right_alt
Determine the size of the largest perfect subtree without considering the kth.
- arrow_right_alt
Find the size of the smallest perfect subtree.
- arrow_right_alt
Return the number of perfect subtrees instead of their size.