链接：删除二叉搜索树中的节点

删除一个节点，分3种情况

1. 待删除节点是叶子节点，这时之间将执行该节点的指针设置为空即可。
2. 待删除节点不是叶节点，且有右子节点，这时可以找到该节点的后继节点，将待删除节点的值设置为后继节点的值，然后再在右子树中删除后继节点。
   3.待删除节点不是叶子节点，没有右子节点，但是右左子节点，这时可以找到该节点的前驱节点，将待删除节点的值设置为前驱节点的值，然后在左子树中删除前驱节点。

关于二叉搜索树的前驱、后继节点

这里的前驱节点计算方法是限制节点有左子节点的条件下，找前驱节点的方法。如果一个子树没有左子节点，它的前驱节点需要往上找它的第一个通过right指针链接子树的父节点。后继节点也有类似情况，这些方法在红黑树的实现中有用到。

代码小技巧

一般来说，删除树的叶子节点，需要知道指向该叶子节点的父节点、以及该叶子节点是左、右孩子，将对应的指针设置为空。这个操作在没有指向父节点的指针时会很麻烦。但是可以利用递归函数的返回值来简单快捷实现这个效果，root.left = delete(root.left, key)。delete函数在删除节点的同时，其返回值还能用了更新root.left这个指针的指向。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
        root = self.delete(root, key)
        return root

    def delete(self, root, key):
        if not root:
            # print("root is None")
            return None
        # print("root.val:{}, root.left:{}, root.right:{}".format(root.val, root.left, root.right))
        if root.val < key:
            res = self.delete(root.right, key)
            root.right = res
        elif root.val > key:
            res = self.delete(root.left, key)
            root.left = res
        else:
            if not (root.left or root.right):
                root = None
            elif root.left:
                root.val = self.predecessor(root)
                root.left = self.delete(root.left, root.val)
            else:
                root.val = self.successor(root)
                root.right = self.delete(root.right, root.val)

        # print("return root:{}".format(root))
        return root

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

    def successor(self, root):
        root = root.right
        while root.left:
            root = root.left
        return root.val