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
Python Solution 1:
# 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
"""
#find the target and its parent.
parent = None
cur = root
while cur and cur.val != key:
parent = cur
if cur.val < key:
cur = cur.right
else:
cur = cur.left
if not cur: return root
# if the target is a leaf.
if not cur.left and not cur.right:
if not parent: return
if parent.left == cur:
parent.left = None
else: parent.right = None
return root
# find the leaf.
if cur.left:
father = cur
son = cur.left
while son.right:
father = son
son = son.right
cur.val = son.val
if father.left == son:
father.left = son.left
else:
father.right = son.left
return root
father = cur
son = cur.right
while son.left:
father = son
son = son.left
cur.val = son.val
if father.left == son:
father.left = son.right
else:
father.right = son.right
return root
Python Solution 2:
# 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
if root.val < key:
root.right = self.deleteNode(root.right, key)
return root
if root.val > key:
root.left = self.deleteNode(root.left, key)
return root
if not root.left:
return root.right
if not root.right:
return root.left
father = root
son = root.left
while son.right:
father = son
son = son.right
root.val = son.val
if father.left == son:
father.left = son.left
else:
father.right = son.left
return root
Python Solution 3:
# 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
"""
parent = None
cur = root
while cur and cur.val != key:
parent = cur
if cur.val > key:
cur = cur.left
else:
cur = cur.right
if not cur: return root
if not cur.left:
if not parent: return cur.right
if parent.left == cur:
parent.left = cur.right
else:
parent.right = cur.right
return root
father = cur
son = cur.left
while son.right:
father = son
son = son.right
cur.val = son.val
if father.left == son:
father.left = son.left
else:
father.right = son.left
return root
Summary:
- when solving BST problem, merge BST's attribute and recursive.
LeetCode: 450. Delete Node in a BST
近期评论