Delete Node in a BST

Description

Given a root node reference of a BST and a key, delete the node with the given key in the BST. Return the root node reference (possibly updated) of the BST.

Basically, the deletion can be divided into two stages:

1. Search for a node to remove.
2. If the node is found, delete the node.

Follow up: Can you solve it with time complexity O(height of tree)?

 

Example 1:

Input: root = [5,3,6,2,4,null,7], key = 3
Output: [5,4,6,2,null,null,7]
Explanation: Given key to delete is 3. So we find the node with value 3 and delete it.
One valid answer is [5,4,6,2,null,null,7], shown in the above BST.
Please notice that another valid answer is [5,2,6,null,4,null,7] and it's also accepted.

Example 2:

Input: root = [5,3,6,2,4,null,7], key = 0
Output: [5,3,6,2,4,null,7]
Explanation: The tree does not contain a node with value = 0.

Example 3:

Input: root = [], key = 0
Output: []

 

Constraints:

• The number of nodes in the tree is in the range [0, 104].
• -105 <= Node.val <= 105
• Each node has a unique value.
• root is a valid binary search tree.
• -105 <= key <= 105

Solution(javascript)

/*
 * @lc app=leetcode id=450 lang=javascript
 *
 * [450] Delete Node in a BST
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} key
 * @return {TreeNode}
 */
const deleteNode = function (root, key) {
  const min = (node) => {
    let current = node
    while (current && current.left) {
      current = current.left
    }
    return current
  }
  const deleteMin = (node) => {
    if (!node.left) {
      return node.right
    }
    node.left = deleteMin(node.left)
    return node
  }
  const deleteHelper = (node) => {
    if (!node) {
      return null
    }
    if (node.val > key) {
      node.left = deleteHelper(node.left)
      return node
    }
    if (node.val < key) {
      node.right = deleteHelper(node.right)
      return node
    }
    if (!node.left || !node.right) { // 没有子节点或者只有一个子节点
      return node.left || node.right
    }

    // 两个子节点
    const minNode = min(node.right)
    node.val = minNode.val
    node.right = deleteMin(node.right)
    return node
  }
  return deleteHelper(root)
}
// @lc code=end