450. 删除二叉搜索树中的节点

# Definition for a binary tree node.'''搜索二叉树，是一个左子树小于根节点小于右子树的特殊二叉树。'''# 这道题使用递归的方法来做，有删除的节点有四种情况，# 1，是叶子节点。没有孩子。# 2，有一个左孩子。直接让左孩子即为就好了。# 3，有一个右孩子。 直接让右孩子即为。# 4，左右孩子都有。 有两种办法。#  （1），找到左孩子值最大的节点，左子树一直向右遍历。#   （2），找到右孩子值最小的几点，右子树一直向左遍历。class TreeNode:    def __init__(self, val=0, left=None, right=None):        self.val = val        self.left = left        self.right = rightclass Solution:    def deleteNode(self, root: TreeNode, key: int) -> TreeNode:        # 如果root为空，直接返回。        if root is None:            return root        # 先寻找到需要删除的节点。        if root.val > key:            root.left = self.deleteNode(root.left,key)        elif root.val < key:            root.right = self.deleteNode(root.right,key)        else:            # 没有孩子，那么直接删除，然后返回。            if root.left is None and root.right is None:                root = None                return root            # 有左孩子，让左孩子即为。            elif root.left and root.right is None:                tmp = root.left                root = None                return tmp            # 只有右孩子，让右孩子即为。            elif root.right and root.left is None:                tmp = root.right                root = None                return tmp            else:                # # 左右孩子都存在。1，寻找右孩子的最小值。                # curr = root.right                # # 右孩子向左递归，就是右孩子的最小值。                # while curr.left:                #     curr = curr.left                # # 让右孩子的最小值即为。                # root.val = curr.val                # # 删除掉那个节点。                # root.right = self.deleteNode(root.right,curr.val)

                # 2，寻找左孩子的最大值。                curr = root.left                while curr.right:                    curr = curr.right                root.val = curr.val                root.left = self.deleteNode(root.left,curr.val)        return root