首先要找到目标数值，然后看该节点的左右子树情况，
1.没有左子树，返回其右子树
2.没有右子树，返回其左子树
3.左右子树都有，查找到其右子树的最小值的节点，替换掉被删除的节点，并删除找到的最小节点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| 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:
if not root.right:
left = root.left
return left
else:
right = root.right
while right.left:
right = right.left
root.val, right.val = right.val, root.val
root.left = self.deleteNode(root.left, key)
root.right = self.deleteNode(root.right, key)
return root
|