1. 题目描述

给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。一般来说，删除节点可分为两个步骤：

  1. 首先找到需要删除的节点；
  2. 如果找到了，删除它。


说明： 要求算法时间复杂度为 O(h)，h 为树的高度。
示例:**

  1. root = [5,3,6,2,4,null,7]
  2. key = 3
  3.     5
  4.    / \
  5.   3   6
  6.  / \   \
  7. 2   4   7
  8. 给定需要删除的节点值是 3，所以我们首先找到 3 这个节点，然后删除它。
  9. 一个正确的答案是 [5,4,6,2,null,null,7], 如下图所示。
  10.     5
  11.    / \
  12.   4   6
  13.  /     \
  14. 2       7
  15. 另一个正确答案是 [5,2,6,null,4,null,7]。
  16.     5
  17.    / \
  18.   2   6
  19.    \   \
  20.     4   7

2. 解题思路

我们知道，二叉搜索树的左子树总是比根节点小，右子树总是比根节点大，所以可以将根节点的值与要删除的 key 值对比，就知道要删除的值在哪个位置：

  • 如果key 和根节点相等，那么就删除当前的根节点，退出递归；
  • 如果key 比根节点值大，那么就要递归右子树去查找；
  • 如果key 比根节点值小，那么就要递归左子树去查找；

当我们找到需要删除的节点时，会有以下四种情况：

  • 待删除的节点的左右子节点均为空，那么就直接删除当前节点即可；
  • 待删除的节点存在左子节点，而右子节点为空，那么就当前节点设置为左子节点的值；
  • 待删除的节点存在右子节点，而左子节点为空，那么就当前节点设置为右子节点的值；
  • 带删除的节点同时存在左子子节点，那么就要找到比当前节点小的最大节点（或者比当前节点大的最小节点）来替换掉当前的节点（下面代码中，我们是找的是比当前节点大的最小节点）；

复杂度分析：

  • 时间复杂度：O(logN)。在算法的执行过程中，我们一直在树上向左或向右移动。首先先用 O(H) 的时间找到要删除的节点，H指得是从根节点到要删除节点的高度。然后删除节点需要 O(H) 的时间，H指的是从要删除节点到替换节点的高度。由于 O(H+ H)=O(H)，H 指得是树的高度，若树是一个平衡树，则 H = logN。

  • 空间复杂度：O(H)，递归时堆栈使用的空间，其中 H 是树的高度。

    3. 代码实现

    ```javascript /**

    • 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){

      1. return root

      }

      if(root.val > key){

      1. root.left = deleteNode(root.left, key)

      }else if(root.val < key){

      1. root.right = deleteNode(root.right, key)

      }else{

      1. if(!root.left && !root.right){
      2.     root = null
      3. }else if(root.left && !root.right){
      4.     root = root.left
      5. }else if(!root.left && root.right){
      6.     root = root.right
      7. }else if(root.left && root.right){
      8.     let last = root.right
      9.     while (last.left) {
      10.         last = last.left
      11.     }
      12.     root.val = last.val
      13.     root.right = deleteNode(root.right, last.val)
      14. }

      } return root

}; ```

4. 提交结果

image.png