None recursive version, what's the issue


  • 0
    Z

    can't figure out the issue

    class Solution(object):
        def deleteNode(self, root, key):
            """
            :type root: TreeNode
            :type key: int
            :rtype: TreeNode
            """
            found = [False]
            dummy = TreeNode(None)
            dummy.left = root
    
            c2p = {}
            def leftMost(l):
                tr = l
                while l:
                    if l.left: c2p[l.left] = l
                    l = l.left
                return l if l else tr
            def succUpwd(c):
                p = c2p[c]
                while p != dummy and c == p.right:
                    c = p 
                    p = c2p[c]
                return c
            def traverse(parent,nd):
                if found[0]: return
                if nd is None: return
                c2p[nd] = parent
                traverse(nd, nd.left)
                
                if nd.val == key: 
                    if not nd.left and not nd.right:
                        if nd == parent.left: parent.left = None
                        if nd == parent.right: parent.right = None
                    else:
                        toDel = None
                        if nd.right:
                            c2p[nd.right] = nd
                            toDel = leftMost(nd.right) 
                        else: 
                            toDel = succUpwd(nd)
                        pDel = c2p[toDel]
                        nd.val = toDel.val
                        
                        if toDel == pDel.left: pDel.left = toDel.left
                        if toDel == pDel.right: pDel.right = toDel.left
                    found[0] = True
                    
                    
                traverse(nd, nd.right)
                
            traverse(dummy,root)
            return dummy.left
    

Log in to reply
 

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