A iterative Python solution, idea from CLRS.


  • 0
    A

    Just a standard delete operation in CLRS.

    I don't like the way in my code which is used to keep node's parent.
    I don't like pass it as an function argument either.

    So, guys, which way to keep the node's parent is better? or maybe there's a smarter way.

    class Solution(object):
        def deleteNode(self, root, key):
            """
            :type root: TreeNode
            :type key: int
            :rtype: TreeNode
            """
            # iteratively
            # idea from CLRS
            
            current = root
            self.previous = None
            self.root = root
            
            while current and current.val != key:
                self.previous = current
                
                if current.val < key:
                    current = current.right
                else:
                    current = current.left
            
            if not current: return self.root
            
            if not current.right:
                self.transplant(current.left, current)
            elif not current.left:
                self.transplant(current.right, current)
            else:
                tmp = self.previous   # find_min operation may change the previous, which is current's parent
                successor = self.find_min(current.right)
                if successor != current.right:
                    self.transplant(successor.right, successor)
                    successor.right = current.right
                
                self.previous = tmp    # revocer current's parent 
                
                self.transplant(successor, current)
                successor.left = current.left
            return self.root
    
    
        def transplant(self, from_node, to_node):
            to_parent = self.previous
            if not to_parent:
                self.root = from_node
            elif to_node == to_parent.left:
                to_parent.left = from_node
            else:
                to_parent.right = from_node
        
        
        def find_min(self, root):
            assert(root is not None)
            
            while root.left:
                self.previous = root
                root = root.left
            return root
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.