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.

Difficulty: interview

Starter code:

# 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 = right
class Solution:
    def pruneTree(self, root: TreeNode) -> TreeNode:
        

Solutions:
# 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 = right
class Solution:
    
    def pruneTreeHelper(self, root: TreeNode) -> TreeNode:
        if not root:
            return None
        
        left = self.pruneTreeHelper(root.left)
        right = self.pruneTreeHelper(root.right)
        
        if not left:
            root.left = None
        
        if not right:
            root.right = None
        
        if root.val == 0 and root.right is None and root.left is None:
            return None
        else:
            return root
    
    def pruneTree(self, root: TreeNode) -> TreeNode:
        return self.pruneTreeHelper(root)

# 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 = right
class Solution:
    def pruneTree(self, root: TreeNode) -> TreeNode:
        
        if not root:
            return None 
        
        root.left =self.pruneTree(root.left)
        
        root.right= self.pruneTree(root.right)
        if not root.left and not root.right and root.val ==0:
            return None
        
        return root
        


# 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 = right
class Solution:
    def pruneTree(self, root: TreeNode) -> TreeNode:
        
        def prune(node: TreeNode) -> bool:
            
            
            if not node:
                return True
            
            # if node is 1, the tree with node as root does not need to be pruned

            
            left_prune = prune(node.left)
            right_prune = prune(node.right)
            
            if prune(node.left):
                node.left = None
            if prune(node.right):
                node.right = None
            
            return (node.val == 0) and left_prune and right_prune
        
        
        
        if prune(root):
            return None
        
        return root


# 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 = right
class Solution:
    def pruneTree(self, root: TreeNode) -> TreeNode:
        def check(node):
            
            if not node.left:
                l=True
            else:
                l=check(node.left)
            if not node.right:
                r=True
            else:
                r=check(node.right)
            if l:
                node.left=None
            if r:
                node.right=None
            return l and r and node.val==0
        ans=TreeNode()
        ans.right=root
        check(ans)
        return ans.right

# 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 = right
class Solution:
    def pruneTree(self, root: TreeNode) -> TreeNode:
        def dfs(node):
            if not node:
                return False
            a1 = dfs(node.left)
            a2 = dfs(node.right)
            if not a1:node.left=None
            if not a2:node.right=None
            return node.val ==1 or a1 or a2
        return root if dfs(root) else None



# 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 = right
class Solution:
    def pruneTree(self, root: TreeNode) -> TreeNode:
        
        
        def prune_tree_helper(root):
            if root:
                curr_res = True if root.val == 0 else False
                left_res = prune_tree_helper(root.left)
                right_res = prune_tree_helper(root.right)
                if left_res:
                    root.left = None
                if right_res:
                    root.right = None
                return curr_res and left_res and right_res
            else:
                return True
        res = prune_tree_helper(root)
        if res:
            return None
        else:
            return root


# 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 = right
class Solution:
    def pruneTree(self, root: TreeNode) -> TreeNode:
        return self.dfs(root)
    
    def dfs(self, root):
        if not root:
            return None
        
        root.left = self.dfs(root.left)
        root.right = self.dfs(root.right)
        
        # Bubble up None
        if not root.val and not root.left and not root.right:
            return None
        
        return root
        


# 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 = right
class Solution:
    def pruneTree(self, root: TreeNode) -> TreeNode:
        if not root:
            return None
        l = self.pruneTree(root.left)
        r = self.pruneTree(root.right)
        if not l and not r and root.val == 0:
            return None
        root.left = l
        root.right = r
        return root

# 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 = right
class Solution:
    def pruneTree(self, root: TreeNode) -> TreeNode:
        return root if self.dfs(root) else None
    
    def dfs(self, root):
        if not root:
            return False
        l = self.dfs(root.left)
        r = self.dfs(root.right)
        if not l:
            root.left = None
        if not r:
            root.right = None
        return root.val == 1 or l or r

# 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 = right
class Solution:
    def pruneTree(self, root: TreeNode) -> TreeNode:
        def helper(root):
            if not root:
                return False
            lone = helper(root.left)
            rone = helper(root.right)
            if not lone:
                root.left = None
            if not rone:
                root.right = None
            if root.val == 1 or lone or rone:
                return True
            else:
                return False
                
        if helper(root):
            return root
        else:
            return None

# 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 = right
class Solution:
    def pruneTree(self, root: TreeNode) -> TreeNode:
        if root == None:
            return None
        left_sub = self.pruneTree(root.left)
        right_sub = self.pruneTree(root.right)
        if root.val  == 0 and left_sub == None and right_sub == None:
            return None
        root.left  = left_sub
        root.right = right_sub
        return root