# [LeetCode 814. Binary Tree Pruning ](https://leetcode.com/explore/challenge/card/july-leetcoding-challenge-2021/611/week-4-july-22nd-july-28th/3824/)
### Daily challenge Jul 23, 2021 (MEDIAN)

>Given the `root` of a binary tree, return the same tree where every subtree (of the given tree) not containing a `1` has been removed.
>
>A subtree of a node node is node plus every node that is a descendant of node.


:::info
**Example 1:**
**Input:** root = [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.
:::


:::info
**Example 2:**
**Input:** root = [1,0,1,0,0,0,1]
**Output:** [1,null,1,null,1]
:::


:::info
**Example 3:**
**Input:** root = [1,1,0,1,1,0,1,0]
**Output:** [1,1,0,1,1,null,1]
:::

:::warning
**Constraints:**
* The number of nodes in the tree is in the range [1, 200].
* Node.val is either 0 or 1.
:::

---

### Approach 1 : Recursion :bulb:
**`4 ms ( % )`** **`O()`**

首先走到 `tree` 的最底層，再慢慢向上層判斷。
>1. 若 **`root == NULL`** ---> 回傳 `NULL`。
>2. 若 **`root->val == 0 && root->left == NULL && root->right == NULL`**。
>---> 表示該 `root` 應該被 `remove`，回傳 `NULL`。
>3. Otherwise ---> 回傳 `root`。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */

class Solution {
public:
    TreeNode* cut(TreeNode* root) {
        if(root == NULL)   return NULL;
        
        root->left = cut(root->left);
        root->right = cut(root->right);
        
        if(root->val == 0 && root->left == NULL && root->right == NULL)   return NULL;
        return root;
    }
    
    TreeNode* pruneTree(TreeNode* root) {        
        return cut(root);
    }
};