1325.delete-leaves-with-a-given-value.md

1325. Delete Leaves With a Given Value

Clarification Questions

• Does the target always exist the tree?

Test Cases

Normal Cases

Input: 
        1
       / \
      2   3
     /   / \
    2   2   4
   /   /   /
  2   2   2
target = 2
Output: 
        1
         \
          3
           \
            4

Edge / Corner Cases

• The target exists, but not in leaf.
• The remaining node becomes the new leaf after deleting, and we have to delete the new leaf.

Input: 
        2
     /     \
    3       4
   / \     / 
  3   7   3
target = 2

Output: 
        2
           \
            4

• The entire tree will be deleted.

Input:
2
target = 2

Output: []

Input: 
     2
   /   \
  2     2
 / \   / \
2  2   2  2
target = 2

Output: []

Recursive

For problem statement Note that once you delete a leaf node with value target, if its parent node becomes a leaf node and has the value target, it should also be deleted, so we have to process the children first (postorder), then we check the root if it becomes the leaf and to delete or not.

fun removeLeafNodes(root: TreeNode?, target: Int): TreeNode? {
    if (root == null) return null
    root.left = removeLeafNodes(root.left, target)
    root.right = removeLeafNodes(root.right, target)

    // After deleting the children, check if the root becomes the leaf and if to delete or not.
    if (root.left == null && root.right == null && root.`val` == target) {
        return null
    }
    return root
}

• Time Complexity: O(n).
• Space Complexity: O(h).