https://leetcode.com/problems/delete-node-in-a-bst/
Given a root node reference of a BST and a key, delete the node with the given key in the BST. Return the root node reference (possibly updated) of the BST.
Basically, the deletion can be divided into two stages:
Search for a node to remove.
If the node is found, delete the node.
Note: Time complexity should be O(height of tree).
Example:
root = [5,3,6,2,4,null,7]
key = 3
5
/
3 6
/
2 4 7
Given key to delete is 3. So we find the node with value 3 and delete it.
One valid answer is [5,4,6,2,null,null,7], shown in the following BST.
5
/
4 6
/
2 7
Another valid answer is [5,2,6,null,4,null,7].
5
/
2 6
4 7
Solution(Python)
思路
1.首先递归的寻找要删除的节点。
2.找到要删除的节点后，有下面四种情况：
- 该节点左右子树均为空—返回null
- 该节点只有左子树为空—返回右子树
- 该节点只有右子树为空—返回左子树
- 该节点左右子树均不为空—寻找该节点的右子树中的最小节点，用最小节点的值替代该节点的值，继续递归地去删除右子树中的那个最小节点。
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def deleteNode(self, root, key):
"""
:type root: TreeNode
:type key: int
:rtype: TreeNode
"""
if not root:
return None
if key < root.val:
root.left = self.deleteNode(root.left, key)
elif key > root.val:
root.right = self.deleteNode(root.right, key)
else: # already found then delete
if not root.left:
return root.right
elif not root.right:
return root.left
minNode = self.findMin(root.right)
root.val = minNode.val
root.right = self.deleteNode(root.right, root.val)
return root
def findMin(self, node):
while node.left != None:
node = node.left
return node