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
Simple O(n) iterative in python with comments
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.