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 $\textit{dfs}$ to calculate the size of the perfect binary subtree rooted at the current node, using an array $\textit{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 $\textit{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 $\textit{cnt} = l + r + 1$, and add $\textit{cnt}$ to the array $\textit{nums}$;
Return $\textit{cnt}$.
We call the $\textit{dfs}$ function to calculate the sizes of all perfect binary subtrees. If the length of the array $\textit{nums}$ is less than $k$, return $-1$. Otherwise, sort the array $\textit{nums}$ in descending order and return the $k$-th largest perfect binary subtree size.
The time complexity is $O(n \times \log n)$, 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]}