1080. Insufficient Nodes in Root to Leaf Paths

Given the `root` of a binary tree, consider all root to leaf paths: paths from the root to any leaf.  (A leaf is a node with no children.)

A `node` is insufficient if every such root to leaf path intersecting this `node` has sum strictly less than `limit`.

Delete all insufficient nodes simultaneously, and return the root of the resulting binary tree.

Example 1:

```
Input: root = [1,2,3,4,-99,-99,7,8,9,-99,-99,12,13,-99,14], limit = 1

Output: [1,2,3,4,null,null,7,8,9,null,14]
```

Example 2:

```
Input: root = [5,4,8,11,null,17,4,7,1,null,null,5,3], limit = 22

Output: [5,4,8,11,null,17,4,7,null,null,null,5]```

Example 3:

```
Input: root = [1,2,-3,-5,null,4,null], limit = -1

Output: [1,null,-3,4]```

Note:

1. The given tree will have between `1` and `5000` nodes.
2. `-10^5 <= node.val <= 10^5`
3. `-10^9 <= limit <= 10^9`

1080. Insufficient Nodes in Root to Leaf Paths
``````struct Solution;
use rustgym_util::*;

trait Postorder {
fn postorder(self, limit: i32) -> TreeLink;
}

fn postorder(self, limit: i32) -> TreeLink {
if let Some(node) = self {
let val = node.borrow_mut().val;
let left = node.borrow_mut().left.take();
let right = node.borrow_mut().right.take();
if left.is_none() && right.is_none() {
if val >= limit {
Some(node)
} else {
None
}
} else {
let l = left.postorder(limit - val);
let r = right.postorder(limit - val);
if l.is_some() || r.is_some() {
node.borrow_mut().left = l;
node.borrow_mut().right = r;
Some(node)
} else {
None
}
}
} else {
None
}
}
}

impl Solution {
root.postorder(limit)
}
}

#[test]
fn test() {
let root = tree!(
1,
tree!(
2,
tree!(4, tree!(8), tree!(9)),
tree!(-99, tree!(-99), tree!(-99))
),
tree!(
3,
tree!(-99, tree!(12), tree!(13)),
tree!(7, tree!(-99), tree!(14))
)
);
let limit = 1;
let res = tree!(
1,
tree!(2, tree!(4, tree!(8), tree!(9)), None),
tree!(3, None, tree!(7, None, tree!(14)))
);
assert_eq!(Solution::sufficient_subset(root, limit), res);
let root = tree!(
5,
tree!(4, tree!(11, tree!(7), tree!(1)), None),
tree!(8, tree!(17), tree!(4, tree!(5), tree!(3)))
);
let limit = 22;
let res = tree!(
5,
tree!(4, tree!(11, tree!(7), None), None),
tree!(8, tree!(17), tree!(4, tree!(5), None))
);
assert_eq!(Solution::sufficient_subset(root, limit), res);
let root = tree!(1, tree!(2, tree!(-5), None), tree!(-3, tree!(4), None));
let limit = -1;
let res = tree!(1, None, tree!(-3, tree!(4), None));
assert_eq!(Solution::sufficient_subset(root, limit), res);
}
``````