Python iterative solution, easy to understand


  • 0
    S
    class Solution(object):
        def deleteNode(self, root, key):
            """
            :type root: TreeNode
            :type key: int
            :rtype: TreeNode
            """
            # 1. find the node to be deleted
            dummy = TreeNode(0)
            dummy.left = root
            p = root 
            parent = dummy
            while p is not None and p.val != key:
                parent = p
                if p.val > key:
                    p = p.left
                else:
                    p = p.right
            if p is None: # not found
                return root
            # 2. find the minimum of p's right subtree
            q_parent = p
            q = p.right
            if q is None: # p has no right subtree, just promote its left subtree
                if parent.left == p:
                    parent.left = p.left
                else:
                    parent.right = p.left
            else:
                while q.left is not None:
                    q_parent = q
                    q = q.left
                # exchange value between the minimum q and p
                p.val = q.val
                # promote q's right child
                if q_parent.left == q:
                    q_parent.left = q.right
                else:
                    q_parent.right = q.right
            return dummy.left

Log in to reply
 

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