python recursive and iterative

  • 0


    I got the almost the same code as


    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
                    nodeFound = nodeFound.left
            if nodeFound is None:
                # no node!
                return root
            subRoot = None
            if nodeFound.left is None:
                subRoot = nodeFound.right
                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.