Iteration in Python

  • 0

    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
                # found it
        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
                parent.right = replace.right
            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.