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
• The given binary tree will have between 1 and 3000 nodes.
• Each node's value is between [1, 1000].

Solution(javascript)

/**
 * 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}
 */
// const removeLeafNodes = function (root, target) {
//   if (!root) {
//     return null
//   }
//   const deleteLeaf = (node) => {
//     if (
//       !node
//       || node.left
//       || node.right
//       || !node.parent
//       || node.val !== target
//     ) {
//       return
//     }
//     const { parent } = node
//     if (parent) {
//       if (parent.left === node) {
//         parent.left = null
//       } else {
//         parent.right = null
//       }
//     }
//     node.parent = null
//     deleteLeaf(parent)
//   }
//   const aux = (node, prev, f) => {
//     if (!node) {
//       return
//     }
//     aux(node.left, node, f)
//     f(node, prev)
//     aux(node.right, node, f)
//   }
//   aux(root, null, (node, prev) => {
//     node.parent = prev
//   })
//   aux(root, null, (node) => {
//     deleteLeaf(node)
//   })
//   return root.val === target && !root.left && !root.right ? null : root
// }

const removeLeafNodes = function (root, target) {
  const aux = (node) => {
    if (!node) {
      return null
    }
    node.left = aux(node.left)
    node.right = aux(node.right)
    return node.val === target && !node.left && !node.right ? null : node
  }
  return aux(root)
}