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
 

Rust Solution

struct Solution;
use rustgym_util::*;

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

impl Postorder for 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 {
    fn sufficient_subset(root: TreeLink, limit: i32) -> TreeLink {
        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);
}

Having problems with this solution? Click here to submit an issue on github.