Binary Tree Pruning

Problem Id: 814 Difficulty: Medium Tag: Tree


Intuition

Just do a BFS (post order) and remove those sub-tree with all '0's.

Solution


# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def pruneTree(self, node: TreeNode) -> TreeNode:
        if node is None:
            return None
        node.left = self.pruneTree(node.left)
        node.right = self.pruneTree(node.right)
        if node.left is None and node.right is None and node.val == 0:
            return None
        return node