495. Prune Zero Branches
A sensor network is arranged as a binary tree whose top node is root. Each node has val equal to 0 (quiet) or 1 (active). Maintenance wants to cut away every part of the network that never reports anything: a node must be removed whenever its whole subtree, meaning the node itself and all of its descendants, contains only zeros.
Remove all such nodes and return the root of the remaining tree. Nodes that stay keep their values and their relative left/right positions. If no node with value 1 exists, every node is removed and the returned tree is empty.
Example 1
- Input:
- root = [1,0,0,0,1,null,0,null,null,null,0]
- Output:
- [1,0,null,null,1]
- Explanation:
The left 0 survives because its right child is a 1; the zero-only right branch and the trailing 0 below that 1 are cut, giving the tree [1,0,null,null,1].
Example 2
- Input:
- root = [0,0,0]
- Output:
- []
- Explanation:
The tree contains no 1, so every node is removed and the result is the empty tree.
Constraints
0 ≤ number of nodes ≤ 105
Node.val is either 0 or 1.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(n)
- Space
- O(h)