You are given the root of a binary tree and an integer k.
Return an integer denoting the size of the kthlargestperfect binarysubtree, 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 non-increasing 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 non-increasing 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 non-increasing 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
Solutions
Solution 1: DFS + Sorting
We define a function dfs to calculate the size of the perfect binary subtree rooted at the current node, using an array nums to record the sizes of all perfect binary subtrees. If the subtree rooted at the current node is not a perfect binary subtree, it returns −1.
The execution process of the function dfs is as follows:
If the current node is null, return 0;
Recursively calculate the sizes of the perfect binary subtrees of the left and right subtrees, denoted as l and r respectively;
If the sizes of the left and right subtrees are not equal, or if the sizes of the left and right subtrees are less than 0, return −1;
Calculate the size of the perfect binary subtree rooted at the current node cnt=l+r+1, and add cnt to the array nums;
Return cnt.
We call the dfs function to calculate the sizes of all perfect binary subtrees. If the length of the array nums is less than k, return −1. Otherwise, sort the array nums in descending order and return the k-th largest perfect binary subtree size.
The time complexity is O(n×logn), and the space complexity is O(n). Here, n is the number of nodes in the binary tree.
1 2 3 4 5 6 7 8 9101112131415161718192021222324
# 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 = rightclassSolution:defkthLargestPerfectSubtree(self,root:Optional[TreeNode],k:int)->int:defdfs(root:Optional[TreeNode])->int:ifrootisNone:return0l,r=dfs(root.left),dfs(root.right)ifl<0orl!=r:return-1cnt=l+r+1nums.append(cnt)returncntnums=[]dfs(root)iflen(nums)<k:return-1nums.sort(reverse=True)returnnums[k-1]
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */funckthLargestPerfectSubtree(root*TreeNode,kint)int{nums:=[]int{}vardfsfunc(*TreeNode)intdfs=func(root*TreeNode)int{ifroot==nil{return0}l,r:=dfs(root.Left),dfs(root.Right)ifl<0||l!=r{return-1}cnt:=l+r+1nums=append(nums,cnt)returncnt}dfs(root)iflen(nums)<k{return-1}sort.Sort(sort.Reverse(sort.IntSlice(nums)))returnnums[k-1]}