k-th-largest-perfect-subtree-size-in-binary-tree

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

You are given the <code>root</code> of a binary tree and an integer <code>k</code>.

Return an integer denoting the size of the <code>kth</code> largest perfect binary subtree, or <code>-1</code> if it doesn&#39;t exist.

A perfect binary tree is a tree where all leaves are on the same level, and every parent has two children.

&nbsp;
Example 1:

<div class="example-block">
Input: root = [5,3,6,5,2,5,7,1,8,null,null,6,8], k = 2

Output: 3

Explanation:

<img alt="" src="https://assets.leetcode.com/uploads/2024/10/14/tmpresl95rp-1.png" style="width: 400px; height: 173px;" />

The roots of the perfect binary subtrees are highlighted in black. Their sizes, in non-increasing order are <code>[3, 3, 1, 1, 1, 1, 1, 1]</code>. 
The <code>2nd</code> largest size is 3.
</div>

Example 2:

<div class="example-block">
Input: root = [1,2,3,4,5,6,7], k = 1

Output: 7

Explanation:

<img alt="" src="https://assets.leetcode.com/uploads/2024/10/14/tmp_s508x9e-1.png" style="width: 300px; height: 189px;" />

The sizes of the perfect binary subtrees in non-increasing order are <code>[7, 3, 3, 1, 1, 1, 1]</code>. The size of the largest perfect binary subtree is 7.
</div>

Example 3:

<div class="example-block">
Input: root = [1,2,3,null,4], k = 3

Output: -1

Explanation:

<img alt="" src="https://assets.leetcode.com/uploads/2024/10/14/tmp74xnmpj4-1.png" style="width: 250px; height: 225px;" />

The sizes of the perfect binary subtrees in non-increasing order are <code>[1, 1]</code>. There are fewer than 3 perfect binary subtrees.
</div>

&nbsp;
Constraints:

<ul>
	<li>The number of nodes in the tree is in the range <code>[1, 2000]</code>.</li>
	<li><code>1 &lt;= Node.val &lt;= 2000</code></li>
	<li><code>1 &lt;= k &lt;= 1024</code></li>
</ul>

kthLargestPerfectSubtree

K-th Largest Perfect Subtree Size in Binary Tree

Balanced Binary Tree

balanced-binary-tree

平衡二叉树

Tree

Depth-First Search

Binary Tree

Sorting

给你一棵 二叉树 的根节点 <code>root</code> 和一个整数<code>k</code>。

返回第 <code>k</code> 大的 完美二叉子树 的大小，如果不存在则返回 <code>-1</code>。

完美二叉树 是指所有叶子节点都在同一层级的树，且每个父节点恰有两个子节点。

&nbsp;

示例 1：

<div class="example-block">
输入： root = [5,3,6,5,2,5,7,1,8,null,null,6,8], k = 2

输出： 3

解释：

<img alt="" src="https://assets.leetcode.com/uploads/2024/10/14/tmpresl95rp-1.png" style="width: 400px; height: 173px;" />

完美二叉子树的根节点在图中以黑色突出显示。它们的大小按非递增顺序排列为 <code>[3, 3, 1, 1, 1, 1, 1, 1]</code>。 
第 <code>2</code> 大的完美二叉子树的大小是 3。
</div>

示例 2：

<div class="example-block">
输入： root = [1,2,3,4,5,6,7], k = 1

输出： 7

解释：

<img alt="" src="https://assets.leetcode.com/uploads/2024/10/14/tmp_s508x9e-1.png" style="width: 300px; height: 189px;" />

完美二叉子树的大小按非递增顺序排列为 <code>[7, 3, 3, 1, 1, 1, 1]</code>。最大的完美二叉子树的大小是 7。
</div>

示例 3：

<div class="example-block">
输入： root = [1,2,3,null,4], k = 3

输出： -1

解释：

<img alt="" src="https://assets.leetcode.com/uploads/2024/10/14/tmp74xnmpj4-1.png" style="width: 250px; height: 225px;" />

完美二叉子树的大小按非递增顺序排列为 <code>[1, 1]</code>。完美二叉子树的数量少于 3。
</div>

&nbsp;

提示：

<ul>
	<li>树中的节点数目在 <code>[1, 2000]</code> 范围内。</li>
	<li><code>1 &lt;= Node.val &lt;= 2000</code></li>
	<li><code>1 &lt;= k &lt;= 1024</code></li>
</ul>