Python recursive solution with comments.


  • 0
    C
    # suppose the root.left part has been upsideDowned,
    # then connect the root node (not root) to the right 
    # side of the right-most node of the already upsideDowned
    # root.left part, root.right to the left side
    def upsideDownBinaryTree(self, root):
        if not root or (not root.left and not root.right):
            return root
        node = self.upsideDownBinaryTree(root.left)
        tmp = node
        while tmp.right:
            tmp = tmp.right
        tmp.right = TreeNode(root.val)
        tmp.left = root.right
        return node

  • 0
    C

    Short iterative Python solution:

    # Iteratively 
    def upsideDownBinaryTree(self, root):
        if not root:
            return root
        l, r = root.left, root.right
        root.left, root.right = None, None
        while l:
            newL, newR = l.left, l.right
            l.left, l.right = r, root
            root, l, r = l, newL, newR
        return root
    

  • 0

    It seems not a good idea to allocate a new node


Log in to reply
 

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