Leetcode 3319. K-th Largest Perfect Subtree Size in Binary Tree

• Leetcode 3319. K-th Largest Perfect Subtree Size in Binary Tree
  • 1. 解题思路
  • 2. 代码实现

• 题目链接：3319. K-th Largest Perfect Subtree Size in Binary Tree

1. 解题思路

这一题其实就是一个很常见的树的遍历，我们自底向上遍历每一个子树，看看其是否是完美二叉树，然后如果是的话将其结果存储下来然后找出第k大的结果即可。

2. 代码实现

给出python代码实现如下：

class Solution:def kthLargestPerfectSubtree(self, root: Optional[TreeNode], k: int) -> int:perfect_subtree = []def dfs(root):nonlocal perfect_subtreeif root is None:return True, 0left_is_perfect, left_cnt = dfs(root.left)right_is_perfect, right_cnt = dfs(root.right)if left_is_perfect and right_is_perfect and left_cnt == right_cnt:perfect_subtree.append(left_cnt + right_cnt + 1)return True, left_cnt + right_cnt + 1else:return False, left_cnt + right_cnt + 1dfs(root)perfect_subtree = sorted(perfect_subtree, reverse=True)return perfect_subtree[k-1] if len(perfect_subtree) >= k else -1

提交代码评测得到：耗时129ms，占用内存17.3MB。