814. Binary Tree Pruning

Question:

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:

  1. The binary tree will have at most 100 nodes. 2, The value of each node will only be 0 or 1.

Solution:

  • Method 1: recursion
    • For this question must make sure that for a single node, we need 2 flags for indicating left and right can be removed, we should initialize them as true. ```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; boolean left = true, right = true; if(root.left != null){ left = pruneNode(root.left); if(left) root.left = null; } if(root.right != null){ right = pruneNode(root.right); if(right) root.right = null; } if(left && right && root.val == 0){ root = null; } return root; } private boolean pruneNode(TreeNode node){ if(node.val == 0 && node.left == null && node.right == null) return true; else{ boolean left = true, right = true; if(node.left != null){ left = pruneNode(node.left); if(left) node.left = null; } if(node.right != null){ right = pruneNode(node.right); if(right) node.right = null; } return (left && right) && node.val == 0; } } } ```
  • Method 2: Divide and conquer ```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; TreeNode left = pruneTree(root.left); root.left = left; TreeNode right = pruneTree(root.right); root.right = right; if(root.val == 0 && root.left == null && root.right == null) root = null; return root; } } ```