題目
給定一個(gè)二叉搜索樹(shù)的根節(jié)點(diǎn) root 和一個(gè)值 key妻怎，刪除二叉搜索樹(shù)中的 key 對(duì)應(yīng)的節(jié)點(diǎn)，并保證二叉搜索樹(shù)的性質(zhì)不變没讲。返回二叉搜索樹(shù)（有可能被更新）的根節(jié)點(diǎn)的引用靖诗。一般來(lái)說(shuō)薛窥，刪除節(jié)點(diǎn)可分為兩個(gè)步驟：首先找到需要?jiǎng)h除的節(jié)點(diǎn)库倘；如果找到了巴元，刪除它。
例：
輸入：root = [5,3,6,2,4,null,7], key = 3
輸出：[5,4,6,2,null,null,7]
解釋?zhuān)航o定需要?jiǎng)h除的節(jié)點(diǎn)值是 3，所以我們首先找到 3 這個(gè)節(jié)點(diǎn)球化，然后刪除它秽晚。
一個(gè)正確的答案是 [5,4,6,2,null,null,7], 如下圖所示。
另一個(gè)正確答案是 [5,2,6,null,4,null,7]赊窥。
方法：遞歸
- 若想要?jiǎng)h除的節(jié)點(diǎn)不存在爆惧，則返回根節(jié)點(diǎn)
- 若想要?jiǎng)h除的節(jié)點(diǎn)存在：
- 若想要?jiǎng)h除的節(jié)點(diǎn)為葉子節(jié)點(diǎn)狸页，那么直接刪除該節(jié)點(diǎn)锨能，即返回 None
- 若想要?jiǎng)h除的節(jié)點(diǎn)的左子樹(shù)為空但右子樹(shù)不為空，那么直接將右子樹(shù)的“根節(jié)點(diǎn)”移至想要?jiǎng)h除的節(jié)點(diǎn)處代替該節(jié)點(diǎn)芍耘，返回右子樹(shù)的“根節(jié)點(diǎn)”
- 若想要?jiǎng)h除的節(jié)點(diǎn)的右子樹(shù)為空但左子樹(shù)不為空址遇，那么直接將左子樹(shù)的“根節(jié)點(diǎn)”移至想要?jiǎng)h除的節(jié)點(diǎn)處代替該節(jié)點(diǎn)，返回左子樹(shù)的“根節(jié)點(diǎn)”
- 若想要?jiǎng)h除的節(jié)點(diǎn)的左右子樹(shù)均不為空斋竞，根據(jù)二叉搜索樹(shù)的定義倔约，想要?jiǎng)h除的節(jié)點(diǎn)的左子樹(shù)的“根節(jié)點(diǎn)”的值一定小于想要?jiǎng)h除的節(jié)點(diǎn)的右子樹(shù)的最小值（即左下角的值），所以將左子樹(shù)的“根節(jié)點(diǎn)”作為右子樹(shù)的最小葉子節(jié)點(diǎn)的左孩子坝初，然后將右子樹(shù)的“根節(jié)點(diǎn)”移至想要?jiǎng)h除的節(jié)點(diǎn)處代替該節(jié)點(diǎn)浸剩，最后返回右子樹(shù)的“根節(jié)點(diǎn)”
- 若想要?jiǎng)h除的節(jié)點(diǎn)值小于此時(shí)節(jié)點(diǎn)的節(jié)點(diǎn)值，那么調(diào)用 deleteNode 函數(shù)鳄袍，繼續(xù)遍歷節(jié)點(diǎn)的左子樹(shù)
- 若想要?jiǎng)h除的節(jié)點(diǎn)值大于此時(shí)節(jié)點(diǎn)的節(jié)點(diǎn)值绢要，那么調(diào)用 deleteNode 函數(shù)，繼續(xù)遍歷節(jié)點(diǎn)的右子樹(shù)
# 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
