3319. 第 K 大的完美二叉子树的大小

🟠   🔖  树 深度优先搜索 二叉树 排序  🔗 力扣 LeetCode

题目

You are given the root of a binary tree and an integer k.

Return an integer denoting the size of the kth largest perfect binary subtree, or -1 if it doesn't exist.

A perfect binary tree is a tree where all leaves are on the same level, and every parent has two children.

Example 1:

Input: root = [5,3,6,5,2,5,7,1,8,null,null,6,8], k = 2

Output: 3

Explanation:

The roots of the perfect binary subtrees are highlighted in black. Their sizes, in decreasing order are [3, 3, 1, 1, 1, 1, 1, 1]. The 2nd largest size is 3.

Example 2:

Input: root = [1,2,3,4,5,6,7], k = 1

Output: 7

Explanation:

The sizes of the perfect binary subtrees in decreasing order are [7, 3, 3, 1, 1, 1, 1]. The size of the largest perfect binary subtree is 7.

Example 3:

Input: root = [1,2,3,null,4], k = 3

Output: -1

Explanation:

The sizes of the perfect binary subtrees in decreasing order are [1, 1]. There are fewer than 3 perfect binary subtrees.

Constraints:

• The number of nodes in the tree is in the range [1, 2000].
• 1 <= Node.val <= 2000
• 1 <= k <= 1024

题目大意

给你一棵 二叉树 的根节点 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 大的完美子树的大小。

如果数组的大小小于 k，返回 -1，否则返回数组中第 k 大的元素。

复杂度分析

• 时间复杂度：O(n)，每个节点遍历一次。
• 空间复杂度：O(n)，用于存储所有完美子树的大小。

代码

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} k
 * @return {number}
 */
var kthLargestPerfectSubtree = function (root, k) {
	let sizes = findPerfectSubtree(root);
	if (sizes.length < k) return -1;

	// 按降序排序
	sizes.sort((a, b) => b - a);
	return sizes[k - 1];
};

var findPerfectSubtree = function (root) {
	let sizes = [];

	// 递归函数，返回当前子树的高度、节点数和是否为完美二叉树
	const dfs = (root) => {
		if (!root) return [0, 0, true];
		const [leftHeight, leftCount, isLeftPerfect] = dfs(root.left);
		const [rightHeight, rightCount, isRightPerfect] = dfs(root.right);

		const rootCount = leftCount + rightCount + 1;

		// 检查是否为完美子树
		if (leftHeight == rightHeight && isLeftPerfect && isRightPerfect) {
			sizes.push(rootCount);
			return [leftHeight + 1, rootCount, true];
		}
		return [Math.max(leftHeight, rightHeight) + 1, rootCount, false];
	};

	dfs(root);
	return sizes;
};

相关题目

题号	标题	题解	标签	难度
110	平衡二叉树	[✓]	树 深度优先搜索 二叉树