1325. Delete Leaves With a Given Value

Description

Given a binary tree root and an integer target, delete all the leaf nodes with value target.

Note that once you delete a leaf node with value target, if it's parent node becomes a leaf node and has the value target, it should also be deleted (you need to continue doing that until you can't).

 

Example 1:

Input: root = [1,2,3,2,null,2,4], target = 2
Output: [1,null,3,null,4]
Explanation: Leaf nodes in green with value (target = 2) are removed (Picture in left). 
After removing, new nodes become leaf nodes with value (target = 2) (Picture in center).

Example 2:

Input: root = [1,3,3,3,2], target = 3
Output: [1,3,null,null,2]

Example 3:

Input: root = [1,2,null,2,null,2], target = 2
Output: [1]
Explanation: Leaf nodes in green with value (target = 2) are removed at each step.

Example 4:

Input: root = [1,1,1], target = 1
Output: []

Example 5:

Input: root = [1,2,3], target = 1
Output: [1,2,3]

 

Constraints:

  • 1 <= target <= 1000
  • Each tree has at most 3000 nodes.
  • Each node's value is between [1, 1000].

My Solution

Source Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} target
 * @return {TreeNode}
 */

var removeLeafNodes = function(root, target) {
  if (root == null) return root;

  //if this is a leaf node with the target value, remove it
  if (root.left === null && root.right === null && root.val === target) {
    return null;
  }

  //if it's not a leaf, then traverse its next two nodes
  var resLeft = removeLeafNodes(root.left, target);
  var resRight = removeLeafNodes(root.right, target);

  //if both of the nodes were leaves matching the target, then they were removed
  //this node is now a leaf node as well and needs to be checked
  if ((resLeft === null) & (resRight === null) && root.val === target) {
    return null;
  }

  root.left = resLeft;
  root.right = resRight;

  return root;
};

Analysis

Despite being a Medium difficulty problem, this one was actually pretty easy. My solution for this is recursive. We start with the root of the tree. If it's a leaf node with the target value, we're done. Otherwise, we look at its left and right nodes. If both of those are leaves with the target value, then they will be removed and the current root node will also become a leaf. If it has the target value, then remove it. That's basically it. Every time we remove a node, we have to make sure that change "bubbles up" the tree.

Let there be n nodes in the tree. We examine each node exactly once. So, the running time for this is just O(n).