1080. Insufficient Nodes in Root to Leaf Paths Medium

1/**
2 * [1080] Insufficient Nodes in Root to Leaf Paths
3 *
4 * Given the root of a binary tree and an integer limit, delete all insufficient nodes in the tree simultaneously, and return the root of the resulting binary tree.
5 * A node is insufficient if every root to leaf path intersecting this node has a sum strictly less than limit.
6 * A leaf is a node with no children.
7 *  
8 * Example 1:
9 * <img alt="" src="https://assets.leetcode.com/uploads/2019/06/05/insufficient-11.png" style="width: 500px; height: 207px;" />
10 * Input: root = [1,2,3,4,-99,-99,7,8,9,-99,-99,12,13,-99,14], limit = 1
11 * Output: [1,2,3,4,null,null,7,8,9,null,14]
12 * 
13 * Example 2:
14 * <img alt="" src="https://assets.leetcode.com/uploads/2019/06/05/insufficient-3.png" style="width: 400px; height: 274px;" />
15 * Input: root = [5,4,8,11,null,17,4,7,1,null,null,5,3], limit = 22
16 * Output: [5,4,8,11,null,17,4,7,null,null,null,5]
17 * 
18 * Example 3:
19 * <img alt="" src="https://assets.leetcode.com/uploads/2019/06/11/screen-shot-2019-06-11-at-83301-pm.png" style="width: 250px; height: 199px;" />
20 * Input: root = [1,2,-3,-5,null,4,null], limit = -1
21 * Output: [1,null,-3,4]
22 * 
23 *  
24 * Constraints:
25 * 
26 * 	The number of nodes in the tree is in the range [1, 5000].
27 * 	-10^5 <= Node.val <= 10^5
28 * 	-10^9 <= limit <= 10^9
29 * 
30 */
31pub struct Solution {}
32use crate::util::tree::{TreeNode, to_tree};
33
34// problem: https://leetcode.com/problems/insufficient-nodes-in-root-to-leaf-paths/
35// discuss: https://leetcode.com/problems/insufficient-nodes-in-root-to-leaf-paths/discuss/?currentPage=1&orderBy=most_votes&query=
36
37// submission codes start here
38
39// Definition for a binary tree node.
40// #[derive(Debug, PartialEq, Eq)]
41// pub struct TreeNode {
42//   pub val: i32,
43//   pub left: Option<Rc<RefCell<TreeNode>>>,
44//   pub right: Option<Rc<RefCell<TreeNode>>>,
45// }
46// 
47// impl TreeNode {
48//   #[inline]
49//   pub fn new(val: i32) -> Self {
50//     TreeNode {
51//       val,
52//       left: None,
53//       right: None
54//     }
55//   }
56// }
57use std::rc::Rc;
58use std::cell::RefCell;
59impl Solution {
60    pub fn sufficient_subset(root: Option<Rc<RefCell<TreeNode>>>, limit: i32) -> Option<Rc<RefCell<TreeNode>>> {
61        Some(Rc::new(RefCell::new(TreeNode::new(0))))
62    }
63}
64
65// submission codes end
66
67#[cfg(test)]
68mod tests {
69    use super::*;
70
71    #[test]
72    fn test_1080() {
73    }
74}
75