156. Binary Tree Upside Down

[huimeich]

Given a binary tree where all the right nodes are either leaf nodes with a sibling (a left node that shares the same parent node) or empty, flip it upside down and turn it into a tree where the original right nodes turned into left leaf nodes. Return the new root.

Example:

Input: [1,2,3,4,5]

1

/ \ 2 3 / \ 4 5

Output: return the root of the binary tree [4,5,2,#,#,3,1]

4 / \ 5 2 / \ 3 1

[huimeich]

def upsideDownBinaryTree(self, root: TreeNode) -> TreeNode:
    stack = [(root, None)]
    node = root
    while(node):
        stack.append((node.left, node))
        node = node.left
    head = None
    while stack:
        (node, root) = stack.pop()
        if not node:
            head = root
            continue
        node.left = root.right if root else None
        node.right = root
    return head

[huimeich]

def upsideDownBinaryTree(self, root: TreeNode) -> TreeNode:
    newroot = root
    if not root: return root
    while newroot.left:
        newroot = newroot.left
    def helper(node):
        if not node:
            return node
        l, r = helper(node.left), helper(node.right)
        if l:
            l.left = r
            l.right = node
        node.left = node.right = None
        return node
    helper(root)
    return newroot