题目要求

题目给定一个二叉搜索树的根节点 root 和一个值 key。
要求删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。
一般来说，删除节点可分为两个步骤：

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

其次要求算法时间复杂度为 O(h)，h 为树的高度。

解题思路

如何找到需要删除的节点？

根据题目要求，我们肯定是要从上到下进行搜索的。其次，我们也要充分利用BST的性质，可以在每轮递归中比较key和根节点的大小，决定到左子树还是右子树里搜寻（这些技巧我们在LeetCode 236中也用到过）。

如何进行删除？

删除节点主要有三种情况：

• 节点只存在左子树，那么我们直接用左子树代替根节点即可；
• 节点只存在右子树，同样地，我们直接用右子树代替根节点；
• 同时存在左右子树是比较复杂的情况，这是我们重点关注的情况。

这里我们优先采用右子树替换根节点的原则（当然左子树也可以）。
当我们找到需要删除的节点后，必须以右子树的最小节点（也就是右子树最左的节点）来代替被删除的节点，以下图的例子来说明：

这幅图中,如果我们删除节点3，则必须以先节点4替换节点3，再在下两轮递归中，把节点3去掉。
这样才能保持BST的性质不发生变化，满足题目要求，下面给出代码。

class Solution(object):
    def deleteNode(self, root, key):
        """
        :type root: TreeNode
        :type key: int
        :rtype: TreeNode
        """
        if not root:
            return None
        #到左子树里搜索
        if root.val > key:
            root.left = self.deleteNode(root.left, key)
        #到右子树里搜索
        elif root.val < key:
            root.right = self.deleteNode(root.right, key)
        else:
        	# 存在的子树代替根节点
            if not root.left or not root.right:
                root = root.left if root.left else root.right
            else:
                temp = root.right
                # 找到右子树的最小（最左）节点
                while temp.left: 
                    temp = temp.left
                root.val = temp.val
                # 继续在右子树里递归
                root.right = self.deleteNode(root.right, temp.val)
            
        return root