 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 = 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
}
};``````