[Leetcode] 814. Binary Tree Pruning explained

Problem

814. Binary Tree Pruning

Approach

For each tree node, repeat below process.

1. Prune left child.
2. Prune right child.
3. If left and right child is null and this node doesn’t have value 1, return null (prunning).

Code

/**
 * author: jooncco
 * written: 2022. 9. 6. Tue. 13:14:14 [UTC+9]
 **/

class Solution {
    private final int TARGET_VALUE = 1;

    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 != TARGET_VALUE) return null;
        return root;
    }
}

Complexity

• Time: \(O(n)\)
• Space: \(O(n)\)