450.Delete Node in a BST

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:

Search for a node to remove. If the node is found, delete the node. Follow up: Can you solve it with time complexity O(height of tree)?

Example 1:

5                             5
       /   \                         /   \
      3     6        --->           4     6
     /  \     \                    /       \
    2    4     7                  2         7

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.

5
    /   \
   2     6
    \     \
     4     7

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

Analyze

5
    /   \
   3     6
 /  \     \
2    4     7

3
    /   \
   2     4
          \
           6
            \
             7

• 此时删除元素为 5, 此时含有左节点, 可以通过如下方法达到目的:
  • 将删除元素的左下方元素 3 替代删除元素 5;
  • 将左下方元素的右侧最下方子元素 4 衔接删除元素的右下方子元素 6;

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} key
 * @return {TreeNode}
 */
var deleteNode = function(root, key) {
  if (!root) return null
  // if key > root.val, delete node in root.right. Otherwise delete node in root.left.
  if (key > root.val) {
    const rightNode = deleteNode(root.right, key)
    root.right = rightNode
    return root
  } else if (key < root.val) {
    const leftNode = deleteNode(root.left, key)
    root.left = leftNode
    return root
  } else {
    // now root.val === key
    if (!root.left) {
      return root.right
    }
    if (!root.right) {
      return root.left
    }
    // 将删除元素的左下方元素替代删除元素;
    // 将左下方元素的右侧最下方子元素衔接删除元素的右下方子元素;
    const rightChild = root.right
    let newRightChild = root.left
    while (newRightChild.right) {
      newRightChild = newRightChild.right
    }
    newRightChild.right = rightChild
    return root.left
  }
};