Tree Pruning

Given a binary tree root, prune the tree so that subtrees containing all 0s are removed.

Constraints

• n ≤ 100,000 where n is the number of nodes in root

https://binarysearch.com/problems/Tree-Pruning

Examples

Example 1

Input

• root =

Output

• answer =

Explanation

We do not remove the tree at the root or its right child because they still have a 1 as a descendant.

Solution