Simple O(n) iterative in python with comments


  • 0
    S
    class Solution(object):
        def upsideDownBinaryTree(self, root):
            """
            :type root: TreeNode
            :rtype: TreeNode
            """
            def popLeaves(root):
                if root:
                    p       = None
                    sibling = None
                    cur = root
                    while cur.left or cur.right: # as long as cur is not leaf
                        p   = cur           # parent
                        sibling = p.right   # sibling
                        cur     = cur.left  # cur
                    if p : # as long as root is not popped
                        p.left = p.right = None
                    else:
                        root = None # root has been popped!
                    return root, cur, sibling # root, left most leaf, its right sigbling
            
            
            newRoot = None
            cur     = None
            while(root):
                root,node,left = popLeaves(root) # root, node and its right sibling (which will go in left subtree of node)
                if newRoot is None:
                    newRoot = cur = node # first node!
                else:
                    cur.right = node # set right child
                    cur = cur.right  # move to right
                cur.left = left # set right sibling to left child
            
            return newRoot

Log in to reply
 

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