# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution1(object):
def deleteNode(self, root, key):
"""
:type root: TreeNode
:type key: int
:rtype: TreeNode
"""
if not root:
return root
if root.val > key:
root.left = self.deleteNode(root.left,key)
return root
elif root.val < key :
root.right = self.deleteNode(root.right,key)
return root
else:
if not root.left:
successor = root.right
root.right = None
return successor
if not root.right:
successor = root.left
root.left = None
return successor
successor = self.minNode(root.right)
successor.right = self.removeMin(root.right)
successor.left = root.left
root.left = None
root.right = None
return successor
def minNode(self,root):
if not root.left:
return root
return self.minNode(root.left)
def maxNode(self,root):
if not root.right:
return root
return self.maxNode(root.right)
def removeMin(self,root):
if not root.left:
successor = root.right
root.right = None
return successor
root.left = self.removeMin(root.left)
return root
def removeMax(self,root):
if not root.right :
successor = root.left
root.left = None
return successor
root.right = self.removeMax(root.right)
return root
class Solution2(object):
def deleteNode(self, root, key):
"""
:type root: TreeNode
:type key: int
:rtype: TreeNode
"""
if not root:
return root
if root.val > key:
root.left = self.deleteNode(root.left,key)
return root
elif root.val < key :
root.right = self.deleteNode(root.right,key)
return root
else:
if not root.left:
successor = root.right
root.right = None
return successor
if not root.right:
successor = root.left
root.left = None
return successor
successor = self.maxNode(root.left)
successor.left = self.removeMax(root.left)
successor.right = root.right
root.left = None
root.right = None
return successor
def minNode(self,root):
if not root.left:
return root
return self.minNode(root.left)
def maxNode(self,root):
if not root.right:
return root
return self.maxNode(root.right)
def removeMin(self,root):
if not root.left:
successor = root.right
root.right = None
return successor
root.left = self.removeMin(root.left)
return root
def removeMax(self,root):
if not root.right :
successor = root.left
root.left = None
return successor
root.right = self.removeMax(root.right)
return root