LeetCode刷题实战450：删除二叉搜索树中的节点-轻识

算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选！

今天和大家聊的问题叫做 删除二叉搜索树中的节点，我们先来看题面：

https://leetcode-cn.com/problems/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.

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

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

首先找到需要删除的节点；

如果找到了，删除它。

示例

解题

https://blog.csdn.net/xxx_gt/article/details/103673563

首先是利用一个递归函数，每次排除1/2子树的节点，跟我上面的中序遍历相比，大大提高了效率。

递归函数，有两个要点要理解，一个是递归函数的作用，二是它返回的结果是什么。这道题里，这个递归函数的作用就是删除一棵树里的目标节点，返回的是这棵修改后的树的根节点root。

递归过程：

deleteNode(root, key)

如果根节点的值大于目标节点key的值，说明key在左子树，所以递归调用(root.left, key)。key在左子树，也就说明只用修改左子树就行了，右子树不用动，所以可以使 root.left = deleteNode(root.left, key).

如果根节点的值小于目标节点key的值，说明key在右子树，所以递归调用(root.right, key)。同理，rot.rght = deleteNode(root.right, key).

如果根节点的值等于目标节点key的值，说明找到key了，开始进行下一步处理。

（启示：说到二叉搜索树BST时，不仅要想到中序遍历的结果是排好序的，还要想到可以递归，有点像二分查找的模式寻找目标值，提高效率）

删除节点：

经过上一步的递归过程，找到了key，而且key是要调整的这个子树的根节点。

（思考1：竟然不用存储pre节点，是怎么做到连接两个部分的树的？）

当遍历到这个节点时，其实变量名只是起到一个指针的作用，直接修改它的值就行，直接令它的值等于它的继承节点的值。

调整子树：

这部分用到两个子函数：

def successor(root): # 代表中序遍历序列的后一个节点，即比当前节点大的最小节点

root = root.right

while root.left:

root = root.left

return root.val

def predecessor(root): # 代表中序遍历序列的前一个节点，即比当前节点小的最大节点

root = root.left

while root.right:

root = root.right

return root.val

要分三种情况：

整个子树就只有一个节点，也就是根节点是叶节点，这是直接令其等于None就行了。

根节点有右子树，继承节点就选择它的后一个节点（比目标节点大的最小节点）。

root.val = successor(root) # 用它的后继节点代替它

root.right = self.deleteNode(root.right, root.val) # 修改右子树

根节点无右子树但有左子树，继承节点就选择它的前一个节点（比目标节点小的最大节点）。

root.val = predecessor(root) # 用它的后继节点代替它

root.left= self.deleteNode(root.left, root.val) # 修改右子树

代码如下：

class Solution:
    def deleteNode(self, root: TreeNode, key: int) -> TreeNode:
        if not root:
            return None
        def successor(root): # 代表中序遍历序列的下一个节点，即比当前节点大的最小节点
            root = root.right
            while root.left:
                root = root.left
            return root.val

        def predecessor(root):
            root = root.left
            while root.right:
                root = root.right
            return root.val

        if key > root.val: # 如果key大于根节点，则从右子树寻找
            root.right = self.deleteNode(root.right, key)
        elif key < root.val: # 如果key小于根节点，则从左子树寻找
            root.left = self.deleteNode(root.left, key)
        else: # key == 根节点
            if not root.left and not root.right: # 如果根节点是叶节点，则直接删除该节点
                return  None
            if root.right: # 如果该节点有右节点，则要找比它大的下一个节点（后继节点）
                root.val = successor(root) # 用它的后继节点代替它
                root.right = self.deleteNode(root.right, root.val)
            else:
                root.val = predecessor(root)
                root.left = self.deleteNode(root.left, root.val)
        return root