Java

/**

 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 100 nodes.
 The value of each node will only be 0 or 1.

 */

public class Binary_Tree_Pruning {

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        public TreeNode pruneTree(TreeNode root) {
            if (root == null) {
                return root;
            }

            root.left = pruneTree(root.left);
            root.right = pruneTree(root.right);

            // leaf node
            if (root.left == null && root.right == null) {
                if (root.val == 0) {
                    return null;
                } else {
                    return root;
                }
            }

            return root;
        }
    }
}

// OJ: https://leetcode.com/problems/binary-tree-pruning/
// Time: O(N)
// Space: O(logN)
class Solution {
public:
    TreeNode* pruneTree(TreeNode* root) {
        if (!root) return NULL;
        root->left = pruneTree(root->left);
        root->right = pruneTree(root->right);
        return root->left || root->right || root->val ? root : NULL;
    }
};

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

class Solution(object):
    def pruneTree(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """
        if not root: return
        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

Java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode pruneTree(TreeNode root) {
        if (root == null)
            return root;
        Map<TreeNode, TreeNode> childParentMap = new HashMap<TreeNode, TreeNode>();
        List<TreeNode> nodesList = new ArrayList<TreeNode>();
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            nodesList.add(node);
            TreeNode left = node.left, right = node.right;
            if (left != null) {
                childParentMap.put(left, node);
                queue.offer(left);
            }
            if (right != null) {
                childParentMap.put(right, node);
                queue.offer(right);
            }
        }
        for (int i = nodesList.size() - 1; i >= 0; i--) {
            TreeNode node = nodesList.get(i);
            if (node.val == 0) {
                if (node.left == null && node.right == null) {
                    TreeNode parent = childParentMap.get(node);
                    if (parent != null) {
                        if (node == parent.left)
                            parent.left = null;
                        else
                            parent.right = null;
                    } else {
                        root = null;
                        break;
                    }
                }
            }
        }
        return root;
    }
}

// OJ: https://leetcode.com/problems/binary-tree-pruning/
// Time: O(N)
// Space: O(logN)
class Solution {
public:
    TreeNode* pruneTree(TreeNode* root) {
        if (!root) return NULL;
        root->left = pruneTree(root->left);
        root->right = pruneTree(root->right);
        return root->left || root->right || root->val ? root : NULL;
    }
};

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

class Solution(object):
    def pruneTree(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """
        if not root: return
        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

814 - Binary Tree Pruning

All Problems

All Solutions