2025-05-13：第 K 大的完美二叉子树的大小用go语言，给定一棵二

摘要：2025-05-13：第 K 大的完美二叉子树的大小。用go语言，给定一棵二叉树的根节点 root 以及一个整数 k，要求找出第 k 大的满足“完美二叉树”条件的子树的节点数量。这里的“完美二叉树”指的是这样的子树：其所有叶子节点处于同一深度，且每个非叶子节点

2025-05-13：第 K 大的完美二叉子树的大小。用go语言，给定一棵二叉树的根节点 root 以及一个整数 k，要求找出第 k 大的满足“完美二叉树”条件的子树的节点数量。这里的“完美二叉树”指的是这样的子树：其所有叶子节点处于同一深度，且每个非叶子节点都有且仅有两个子节点。如果不存在满足条件的第 k 大子树，则返回 -1。

树中的节点数目在 [1, 2000] 范围内。

输入： 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。

题目来自leetcode3319。

我们需要检查二叉树中的每一个子树，判断它是否是“完美二叉树”，并记录所有符合条件的子树的节点数量。

• 递归检查子树的结构：• 如果当前节点是 nil，则返回 -1（表示空树）。• 递归检查左子树和右子树的高度。• 如果左子树或右子树不是完美二叉树（返回 -2），或者左右子树的高度不相等，则当前子树不是完美二叉树，返回 -2。• 否则，当前子树是完美二叉树，返回其高度（左子树高度 + 1）。• 记录完美二叉树的节点数量：• 完美二叉树的节点数量可以通过高度计算：节点数量 = 2^(h+1) - 1（其中 h 是高度）。• 使用一个数组 cnt 统计不同高度的完美二叉树的数量（cnt[i] 表示高度为 i 的完美二叉树的数量）。• 遍历 cnt 数组，从高到低计算每种高度的完美二叉树的节点数量（1, 3, 7, 15, ...）。• 如果某个高度的完美二叉树数量 c 大于等于 k，则返回该高度的节点数量。• 否则，k -= c，继续检查更小的高度。1. 初始化统计数组 cnt：• cnt 是一个长度为 10 的数组（因为树的最大高度不超过 10，节点数 ≤ 2000）。2. 递归遍历子树：• 从根节点开始，递归检查每个子树是否是完美二叉树。• 如果子树是完美二叉树，则更新 cnt 数组（cnt[height]++）。3. 计算第 k 大的子树大小：• 从最大可能的高度（len(cnt)-1）开始遍历 cnt 数组。• 对于每个高度 i，计算该高度的完美二叉树的节点数量 size = 2^(i+1) - 1。• 如果 cnt[i] >= k，则 size 就是第 k 大的子树大小。• 否则，k -= cnt[i]，继续检查更小的高度。4. 返回结果：• 如果找到符合条件的子树，返回其大小。• 否则，返回 -1。1. 递归遍历所有子树，判断是否是完美二叉树。2. 统计不同高度的完美二叉树的数量。3. 从高到低计算第 k 大的子树大小。4. 时间复杂度 O(N)，空间复杂度 O(N)。package mainimport ( "fmt")type TreeNode struct { Val int Left *TreeNode Right *TreeNode}func kthLargestPerfectSubtree(root *TreeNode, k int)int { cnt := [10]int{} var dfs func(*TreeNode)int dfs = func(node *TreeNode)int { if node == nil { return-1 } leftH := dfs(node.Left) rightH := dfs(node.Right) if leftH == -2 || leftH != rightH { return-2// 不合法 } cnt[leftH+1]++ return leftH + 1 } dfs(root) for i := len(cnt) - 1; i >= 0; i-- { c := cnt[i] if c >= k { return1

Python完整代码如下：

# -*-coding:utf-8-*-from typing importOptionalclassTreeNode:def__init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = rightdefkth_largest_perfect_subtree(root: Optional[TreeNode], k: int) -> int:cnt = [0] * 10# 用于记录不同高度的完美子树数量# 返回值：# -1 表示空节点# -2 表示非法子树（不完美）# 其他 >= 0 表示该节点为根的完美子树的高度defdfs(node: Optional[TreeNode]) -> int:if node isNone:return -1left_h = dfs(node.left)right_h = dfs(node.right)if left_h == -2or left_h != right_h:return -2# 该节点是完美子树根，其高度为 left_h + 1cnt[left_h + 1] += 1return left_h + 1dfs(root)# 从大高度往小高度遍历，计算第 k 大的完美子树大小for h inreversed(range(len(cnt))):c = cnt[h]if c >= k:# 完美二叉树节点数 = 2^(高度+1) - 1，代码中高度是 h，从0开始return (1