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:
200 nodes
.0
or 1
.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);
}