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