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

1/**
2 * [3319] K-th Largest Perfect Subtree Size in Binary Tree
3 *
4 * You are given the root of a binary tree and an integer k.
5 * Return an integer denoting the size of the k^th largest perfect binary <span data-keyword="subtree">subtree</span>, or -1 if it doesn't exist.
6 * A perfect binary tree is a tree where all leaves are on the same level, and every parent has two children.
7 *  
8 * <strong class="example">Example 1:
9 * <div class="example-block">
10 * Input: <span class="example-io">root = [5,3,6,5,2,5,7,1,8,null,null,6,8], k = 2</span>
11 * Output: <span class="example-io">3</span>
12 * Explanation:
13 * <img alt="" src="https://assets.leetcode.com/uploads/2024/10/14/tmpresl95rp-1.png" style="width: 400px; height: 173px;" />
14 * 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].<br />
15 * The 2^nd largest size is 3.
16 * </div>
17 * <strong class="example">Example 2:
18 * <div class="example-block">
19 * Input: <span class="example-io">root = [1,2,3,4,5,6,7], k = 1</span>
20 * Output: <span class="example-io">7</span>
21 * Explanation:
22 * <img alt="" src="https://assets.leetcode.com/uploads/2024/10/14/tmp_s508x9e-1.png" style="width: 300px; height: 189px;" />
23 * 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.
24 * </div>
25 * <strong class="example">Example 3:
26 * <div class="example-block">
27 * Input: <span class="example-io">root = [1,2,3,null,4], k = 3</span>
28 * Output: <span class="example-io">-1</span>
29 * Explanation:
30 * <img alt="" src="https://assets.leetcode.com/uploads/2024/10/14/tmp74xnmpj4-1.png" style="width: 250px; height: 225px;" />
31 * The sizes of the perfect binary subtrees in non-increasing order are [1, 1]. There are fewer than 3 perfect binary subtrees.
32 * </div>
33 *  
34 * Constraints:
35 * 
36 * 	The number of nodes in the tree is in the range [1, 2000].
37 * 	1 <= Node.val <= 2000
38 * 	1 <= k <= 1024
39 * 
40 */
41pub struct Solution {}
42use crate::util::tree::{TreeNode, to_tree};
43
44// problem: https://leetcode.com/problems/k-th-largest-perfect-subtree-size-in-binary-tree/
45// discuss: https://leetcode.com/problems/k-th-largest-perfect-subtree-size-in-binary-tree/discuss/?currentPage=1&orderBy=most_votes&query=
46
47// submission codes start here
48
49// Definition for a binary tree node.
50// #[derive(Debug, PartialEq, Eq)]
51// pub struct TreeNode {
52//   pub val: i32,
53//   pub left: Option<Rc<RefCell<TreeNode>>>,
54//   pub right: Option<Rc<RefCell<TreeNode>>>,
55// }
56// 
57// impl TreeNode {
58//   #[inline]
59//   pub fn new(val: i32) -> Self {
60//     TreeNode {
61//       val,
62//       left: None,
63//       right: None
64//     }
65//   }
66// }
67use std::rc::Rc;
68use std::cell::RefCell;
69impl Solution {
70    pub fn kth_largest_perfect_subtree(root: Option<Rc<RefCell<TreeNode>>>, k: i32) -> i32 {
71        0
72    }
73}
74
75// submission codes end
76
77#[cfg(test)]
78mod tests {
79    use super::*;
80
81    #[test]
82    fn test_3319() {
83    }
84}
85