2021-03-17 | 450. 删除二叉搜索树中的节点

女爷i 2022-11-12 01:40 126阅读 0赞

### 1. 题目描述 ###

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

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

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

root = [5,3,6,2,4,null,7]
    key = 3
        5
       / \
      3   6
     / \   \
    2   4   7
    给定需要删除的节点值是 3，所以我们首先找到 3 这个节点，然后删除它。
    一个正确的答案是 [5,4,6,2,null,null,7], 如下图所示。
        5
       / \
      4   6
     /     \
    2       7
    另一个正确答案是 [5,2,6,null,4,null,7]。
        5
       / \
      2   6
       \   \
        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. 代码实现 ###

/** * 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 root
        }
    
        if(root.val > key){ 
            root.left = deleteNode(root.left, key)
        }else if(root.val < key){ 
            root.right = deleteNode(root.right, key)
        }else{ 
            if(!root.left && !root.right){ 
                root = null
            }else if(root.left && !root.right){ 
                root = root.left
            }else if(!root.left && root.right){ 
                root = root.right
            }else if(root.left && root.right){ 
                let last = root.right
                while (last.left) { 
                    last = last.left
                }
                root.val = last.val
                root.right = deleteNode(root.right, last.val)
            }
        }
        return root
    
    };

### 4. 提交结果 ###

![在这里插入图片描述][2021032119550538.png]

[2021032119550538.png]: /images/20221022/8ecf53a2be9940c58768c3c6cab8e5b3.png?