Given the root of a binary tree, return the same tree where every subtree (of the given tree) not containing a 1 has been removed.
A subtree of a node node is node plus every node that is a descendant of node.
Example 1:
Input: root = [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.
The number of nodes in the tree is in the range [1, 200].
Node.val is either 0 or 1.
Solutions
Solution 1: Recursion
First, we check if the current node is null. If it is, we directly return the null node.
Otherwise, we recursively prune the left and right subtrees and reassign the pruned subtrees to the current node's left and right children. Then, we check if the current node's value is 0 and both its left and right children are null. If so, we return the null node; otherwise, we return the current node.
Time complexity is $O(n)$, and space complexity is $O(n)$. Here, $n$ is the number of nodes in the binary tree.
1 2 3 4 5 6 7 8 9101112131415
# Definition for a binary tree node.# class TreeNode:# def __init__(self, val=0, left=None, right=None):# self.val = val# self.left = left# self.right = rightclassSolution:defpruneTree(self,root:Optional[TreeNode])->Optional[TreeNode]:ifrootisNone:returnrootroot.left=self.pruneTree(root.left)root.right=self.pruneTree(root.right)ifroot.val==0androot.left==root.right:returnNonereturnroot
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */funcpruneTree(root*TreeNode)*TreeNode{ifroot==nil{returnnil}root.Left=pruneTree(root.Left)root.Right=pruneTree(root.Right)ifroot.Val==0&&root.Left==nil&&root.Right==nil{returnnil}returnroot}