814. Binary Tree Pruning

Description

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.

Constraints

• The number of nodes in the tree is in the range [1, 200].

• Node.val is either 0 or 1.

Approach

Links

• Binarysearch

• GeeksforGeeks

• Leetcode

• ProgramCreek

• YouTube

Examples

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.

Example 2

Input: root = [1, 0, 1, 0, 0, 0, 1]

Output: [1, null, 1, null, 1]

Explanation:

Example 3

Input: root = [1, 1, 0, 1, 1, 0, 1, 0]

Output: [1, 1, 0, 1, 1, null, 1]

Explanation:

Solutions

TreeNode

// Definition for a binary tree node.
public class TreeNode {
	int val;
	TreeNode left;
	TreeNode right;
	TreeNode() {}
	TreeNode(int val) { this.val = val; }
	TreeNode(int val, TreeNode left, TreeNode right) {
		this.val = val;
		this.left = left;
		this.right = right;
	}
}

Solution 1

/**
 * Time complexity : 
 * Space complexity : 
 */

class Solution {
    public TreeNode pruneTree(TreeNode root) {
        if(root == null) {
            return null;
        }
        root.left = pruneTree(root.left);
        root.right = pruneTree(root.right);
        if(root.left != null || root.right != null || root.val == 1) {
            return root;
        }
        return null;
    }
}

Follow up