814. Binary Tree Pruning

We are given the head node root of a binary tree, where additionally every node's value is either a 0 or a 1.

Return the same tree where every subtree (of the given tree) not containing a 1 has been removed.

(Recall that the subtree of a node X is X, plus every node that is a descendant of X.)

Example 1:
Input: [1,null,0,0,1]
Output: [1,null,0,null,1]
 
Explanation: 
Only the red nodes satisfy the property "every subtree not containing a 1".
The diagram on the right represents the answer.



Example 2:
Input: [1,0,1,0,0,0,1]
Output: [1,null,1,null,1]




Example 3:
Input: [1,1,0,1,1,0,1,0]
Output: [1,1,0,1,1,null,1]

Note:

  • The binary tree will have at most 200 nodes.
  • The value of each node will only be 0 or 1.

Rust Solution

struct Solution;
use rustgym_util::*;

trait Postorder {
    fn postorder(self) -> Self;
}

impl Postorder for TreeLink {
    fn postorder(self) -> Self {
        if let Some(node) = self {
            let val = node.borrow().val;
            let left = node.borrow_mut().left.take();
            let right = node.borrow_mut().right.take();
            let left = left.postorder();
            let right = right.postorder();
            if left.is_none() && right.is_none() && val == 0 {
                None
            } else {
                tree!(val, left, right)
            }
        } else {
            None
        }
    }
}

impl Solution {
    fn prune_tree(root: TreeLink) -> TreeLink {
        root.postorder()
    }
}

#[test]
fn test() {
    let root = tree!(1, None, tree!(0, tree!(0), tree!(1)));
    let res = tree!(1, None, tree!(0, None, tree!(1)));
    assert_eq!(Solution::prune_tree(root), res);
    let root = tree!(
        1,
        tree!(0, tree!(0), tree!(0)),
        tree!(1, tree!(0), tree!(1))
    );
    let res = tree!(1, None, tree!(1, None, tree!(1)));
    assert_eq!(Solution::prune_tree(root), res);
    let root = tree!(
        1,
        tree!(1, tree!(1, tree!(0), None), tree!(1)),
        tree!(0, tree!(0), tree!(1))
    );
    let res = tree!(1, tree!(1, tree!(1), tree!(1)), tree!(0, None, tree!(1)));
    assert_eq!(Solution::prune_tree(root), res);
}

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