814. Binary Tree Pruning.md

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.

  /**
   * 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

  /**
   * 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;
      }
  }