LeetCode 814 - Binary Tree Pruning

https://leetcode.com/articles/binary-tree-pruning/

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.

Space Complexity: $O(H)$, where $H$ is the height of the tree. This represents the size of the implicit call stack in our recursion.

Prune children of the tree recursively. The only decisions at each node are whether to prune the left child or the right child.

Algorithm

We'll use a function containsOne(node) that does two things: it tells us whether the subtree at this nodecontains a 1, and it also prunes all subtrees not containing 1.

If for example, node.left does not contain a one, then we should prune it via node.left = null.

Also, the parent needs to be checked. If for example the tree is a single node 0, the answer is an empty tree.

  public TreeNode pruneTree(TreeNode root) {

    return containsOne(root) ? root : null;

  }

  public boolean containsOne(TreeNode node) {

    if (node == null)

      return false;

    boolean a1 = containsOne(node.left);

    boolean a2 = containsOne(node.right);

    if (!a1)

      node.left = null;

    if (!a2)

      node.right = null;

    return node.val == 1 || a1 || a2;

  }

https://leetcode.com/problems/binary-tree-pruning/discuss/122730/C%2B%2BJavaPython-Self-Explaining-Solution-and-2-lines
http://zxi.mytechroad.com/blog/tree/leetcode-814-binary-tree-pruning/

  public TreeNode pruneTree(TreeNode root) {

    if (root == null) return root;

    root.left = pruneTree(root.left);

    root.right = pruneTree(root.right);

    return (root.val == 1 || root.left != null || root.right != null) ? root : null;

  }

https://leetcode.com/problems/binary-tree-pruning/discuss/122747/Java-4-lines-Solution-using-Recursion
This is a kind of divide and conquer process. Beginning from the bottom, for null nodes we just return null. If the node is 1, or if there is any child of it is not null, we return itself, otherwise we return null. In this way, only when a node has two null children, and itself is also 0, we return null and the null will be assigned to its parent’s left/right, so we pruned the tree.

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

public TreeNode pruneTree(TreeNode root) {

// base

if (root == null) {

return null;

}

if (root.left == null && root.right == null) {// no need this case

return root.val == 1 ? root : null;

}

TreeNode left = pruneTree(root.left);

root.left = left;// \\

TreeNode right = pruneTree(root.right);

root.right = right;

if (left == null && right == null) {

return root.val == 1 ? root : null;

}

return root;

}