2583. Kth Largest Sum in a Binary Tree Medium

1/**
2 * [2583] Kth Largest Sum in a Binary Tree
3 *
4 * You are given the root of a binary tree and a positive integer k.
5 * The level sum in the tree is the sum of the values of the nodes that are on the same level.
6 * Return the k^th largest level sum in the tree (not necessarily distinct). If there are fewer than k levels in the tree, return -1.
7 * Note that two nodes are on the same level if they have the same distance from the root.
8 *  
9 * <strong class="example">Example 1:
10 * <img alt="" src="https://assets.leetcode.com/uploads/2022/12/14/binaryytreeedrawio-2.png" style="width: 301px; height: 284px;" />
11 * Input: root = [5,8,9,2,1,3,7,4,6], k = 2
12 * Output: 13
13 * Explanation: The level sums are the following:
14 * - Level 1: 5.
15 * - Level 2: 8 + 9 = 17.
16 * - Level 3: 2 + 1 + 3 + 7 = 13.
17 * - Level 4: 4 + 6 = 10.
18 * The 2^nd largest level sum is 13.
19 * 
20 * <strong class="example">Example 2:
21 * <img alt="" src="https://assets.leetcode.com/uploads/2022/12/14/treedrawio-3.png" style="width: 181px; height: 181px;" />
22 * Input: root = [1,2,null,3], k = 1
23 * Output: 3
24 * Explanation: The largest level sum is 3.
25 * 
26 *  
27 * Constraints:
28 * 
29 * 	The number of nodes in the tree is n.
30 * 	2 <= n <= 10^5
31 * 	1 <= Node.val <= 10^6
32 * 	1 <= k <= n
33 * 
34 */
35pub struct Solution {}
36use crate::util::tree::{TreeNode, to_tree};
37
38// problem: https://leetcode.com/problems/kth-largest-sum-in-a-binary-tree/
39// discuss: https://leetcode.com/problems/kth-largest-sum-in-a-binary-tree/discuss/?currentPage=1&orderBy=most_votes&query=
40
41// submission codes start here
42
43// Definition for a binary tree node.
44// #[derive(Debug, PartialEq, Eq)]
45// pub struct TreeNode {
46//   pub val: i32,
47//   pub left: Option<Rc<RefCell<TreeNode>>>,
48//   pub right: Option<Rc<RefCell<TreeNode>>>,
49// }
50// 
51// impl TreeNode {
52//   #[inline]
53//   pub fn new(val: i32) -> Self {
54//     TreeNode {
55//       val,
56//       left: None,
57//       right: None
58//     }
59//   }
60// }
61use std::rc::Rc;
62use std::cell::RefCell;
63impl Solution {
64    pub fn kth_largest_level_sum(root: Option<Rc<RefCell<TreeNode>>>, k: i32) -> i64 {
65        
66    }
67}
68
69// submission codes end
70
71#[cfg(test)]
72mod tests {
73    use super::*;
74
75    #[test]
76    fn test_2583() {
77    }
78}
79