- 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。