python recursive and iterative


  • 0
    F

    recursive:

    I got the almost the same code as https://discuss.leetcode.com/topic/68920/bottom-up-recursive-python-solution-o-log-n-time.

    iterative:

    Keep track of the parent node and the found node. After we find the node whose value is the key, we manipulate the sub tree starting from the found node.

    class Solution(object):
        def deleteNode(self, root, key):
            """
            :type root: TreeNode
            :type key: int
            :rtype: TreeNode
            """
            if root is None:
                return None
    
            parent = None
            nodeFound = root
            while nodeFound and nodeFound.val != key:
                parent = nodeFound
                if nodeFound.val < key:
                    nodeFound = nodeFound.right
                else:
                    nodeFound = nodeFound.left
            if nodeFound is None:
                # no node!
                return root
            
            subRoot = None
            if nodeFound.left is None:
                subRoot = nodeFound.right
            else:
                currNode = nodeFound.left
                while currNode.right is not None:
                    currNode = currNode.right
                currNode.right = nodeFound.right
                subRoot = nodeFound.left
            if parent is None:
                return subRoot
            if parent.left == nodeFound:
                parent.left = subRoot
            if parent.right == nodeFound:
                parent.right = subRoot
            return root
    

Log in to reply
 

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