二叉搜索树删除节点 动画演示

Day60：删除二叉搜索树的某个节点

1 题目

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

一般来说，删除节点可分为两个步骤：

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

说明：要求算法时间复杂度为 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 分析过程

这道题被leetcode定为中等难度级别，实话讲确实属于这类级别，虽然思路不难，但是要想一次写出准确无误的代码，仍然不是一件简单的事情。如果你第一次做这道题能很快写出来，说明你对递归的理解、指针的掌控都达到了一定水平。

这道题的思路很straitforward，根据BST的性质，具体说来分为如下几种情况：

1. 如果被删除节点关键码key小于当前根节点nodei.val，则问题规模直接降阶到左子树中

2. 关键码key大于当前根节点nodei.val，直接到右子树中查找

3. key等于当前根节点nodei.val，又分为4种情况：

   (1). nodei 无左右子树，摘除nodei节点，等于直接返回 None

   (2). nodei 仅有左子树，摘除nodei节点，等于直接返回 nodei.left

   (3). nodei 仅有右子树，摘除nodei节点，等于直接返回 nodei.right

   (4). nodei 都有左右子树，麻烦一点，方法之一：选择以nodei.right为根节点的树中最左侧节点，然后替换nodei

最后返回 nodei.

你看，上面的思路应该足够清晰，但是兑现为代码绝对又是另一回事。你首先要对递归有深刻的理解，其次像链表、二叉树等这类具备递归的数据结构，操作它们节点引用问题要时刻保持清醒，很容易出错。

3 如何写出代码

老规矩，这是我们的节点定义：

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

解决方案对象的主方法，调用自定义方法self.__delNodei(root,key)，这个方法的构思思路是这样：

第一个参数是BST树中的任意节点，因为BST严格满足递归，所以选取任意一个以节点nodei为根的树，删除里面等于key的节点。因此，这个功能一旦实现后，只需在参数赋值时赋值它为root即可。

class Solution(object):
    def deleteNode(self, root, key):
        """
        :type root: TreeNode
        :type key: int
        :rtype: TreeNode
        """
        return self.__delNodei(root,key)

所以关键是如何写出def __delNodei(self,nodei,key)方法，下面我们一步一步分析。

根据上面的4种情况分析，我们在情况4时会用到找树的最左节点，为此先写出这个方法def __findMinNode(self,nodei)：

    # 找到以nodei为根节点树的最小值
    def __findMinNode(self,nodei):
        if not nodei.left:
            return nodei
        while nodei.left:
            nodei = nodei.left
        return nodei

这个比较简单，是链表、二叉树等递归结构的常规迭代思路，注意与向量表i=i+1迭代思路的区别。

先写出第一种大情况，比较简单。因为方法self.__delNodei(nodei.left,key)实现删除等于key的节点后返回对nodei.left节点的引用，所以将nodei的left域指向它即可。

    # 假定已经查询到nodei节点，删除后返回nodei节点的引用
    def __delNodei(self,nodei,key):
        if not nodei:
            return None

        #若满足下面条件，一定在左子树
        if key < nodei.val:
            nodei.left = self.__delNodei(nodei.left,key) # 删除后返回nodei.left节点的引用   

以下面二叉搜索树删除值等于3的节点为例演示，伸入到左子树：

再写出第二种大情况，与上类似：

# 一定在右子树
        elif nodei.val < key:
            nodei.right = self.__delNodei(nodei.right,key)# 删除后返回nodei.right节点的引用

再写出第三种大情况，即找到了等于key节点，又分四种小情况：

被删除节点是叶子节点：直接返回None，就是摘除它了：

 # nodei.val== key，删除nodei
        else:
            # 情况1：被删除节点是叶子节点
            if not nodei.left and not nodei.right:
                return None  # 置为None

第二、三种小情况很相似，跳过被删除节点nodei，直接返回nodei.left 或 node.right 即可：

            # 情况2：被删除节点无右子树
            if not nodei.right:
                return nodei.left # 跳过nodei,返回指向nodei.left，相当于删除了nodei
            # 情况3：被删除节点无左子树
            if not nodei.left:
                return nodei.right

最后一种小情况，大家直接看注释吧：

            # 情况4：被删除节点左右子树都不为空
            # 先找到右子树中最左节点，即右子树最小值节点
            minNodei = self.__findMinNode(nodei.right)
            nodei.val = minNodei.val
            # 删除minNodei，同时返回nodei.right的引用，并赋值给nodei.right
            ## 切记：key已经不是__delNodei的参数key，而是我们找到的minNodei的val值
            nodei.right = self.__delNodei(nodei.right,minNodei.val) 
        
        return nodei