Iteration in Python


  • 0
    M

    '''
    class Solution(object):

    def deleteNode(self, root, key):        
        prev = None
        curr = root
        while curr:
            if key < curr.val:
                prev = curr
                curr = curr.left
            elif key > curr.val:
                prev = curr
                curr = curr.right
            else:
                # found it
                break
            
        if not curr: return root
      
        if curr.right:
            replace, parent = self.findLeftMost(curr.right, curr)
            curr.val = replace.val
            # replace.left must be None. So the only possibility is 'replace' continues to be replaced with its right (replace.right could be None).
            if parent.left == replace:
                parent.left = replace.right
            else:
                parent.right = replace.right
        else:
            if not prev: # deleting root
                root = root.left
            elif prev.left == curr:
                prev.left = curr.left
            elif prev.right == curr:
                prev.right = curr.left
    
        
        return root
            
            
    
    def findLeftMost(self, root, parent):
        while root and root.left:
            parent = root
            root = root.left
        return root, parent
    

    '''


Log in to reply
 

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