 Time Flying  ### 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 = 3Output: [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  }};