题目
给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。一般来说，删除节点可分为两个步骤：首先找到需要删除的节点；如果找到了，删除它。
例：
输入：root = [5,3,6,2,4,null,7], key = 3
输出：[5,4,6,2,null,null,7]
解释：给定需要删除的节点值是 3，所以我们首先找到 3 这个节点，然后删除它。
一个正确的答案是 [5,4,6,2,null,null,7], 如下图所示。
另一个正确答案是 [5,2,6,null,4,null,7]。
方法：递归
- 若想要删除的节点不存在，则返回根节点
- 若想要删除的节点存在：
- 若想要删除的节点为叶子节点，那么直接删除该节点，即返回 None
- 若想要删除的节点的左子树为空但右子树不为空，那么直接将右子树的“根节点”移至想要删除的节点处代替该节点，返回右子树的“根节点”
- 若想要删除的节点的右子树为空但左子树不为空，那么直接将左子树的“根节点”移至想要删除的节点处代替该节点，返回左子树的“根节点”
- 若想要删除的节点的左右子树均不为空，根据二叉搜索树的定义，想要删除的节点的左子树的“根节点”的值一定小于想要删除的节点的右子树的最小值（即左下角的值），所以将左子树的“根节点”作为右子树的最小叶子节点的左孩子，然后将右子树的“根节点”移至想要删除的节点处代替该节点，最后返回右子树的“根节点”
- 若想要删除的节点值小于此时节点的节点值，那么调用 deleteNode 函数，继续遍历节点的左子树
- 若想要删除的节点值大于此时节点的节点值，那么调用 deleteNode 函数，继续遍历节点的右子树
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object):
def deleteNode(self, root, key):
if not root:
return root
if root.val == key:
if not root.left and not root.right:
return None
if not root.left and root.right:
root = root.right
return root
if root.left and not root.right:
root = root.left
return root
if root.left and root.right:
temp = root.right
while temp.left:
temp = temp.left
temp.left = root.left
root = root.right
return root
if key < root.val:
root.left = self.deleteNode(root.left, key)
if key > root.val:
root.right = self.deleteNode(root.right, key)
return root
