Binary Tree Upside Down

Question

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 leaf nodes. Return the new root.

Thoughts

根据题目的意思，原先的和flip过后的binary tree应该看起来像下面这样

  parent              left
 /      \            /    \
left    right      right   parent

or

    parent            left
    /                     \
 left                    parent

可见对于每一个node cur和它的parent

cur.left = parent.right
cur.right = parent

top-down

traversal整个数需要一个pointer,另外还要两个pointer来随时保存parent和parent.right

bottom-up

bottom-up的方法就是从底向上，先recursivly call到leftmost的node,一定是最新的 root bottom-up的方法不用向top-down一样担心overwrite

Solution

top-down

def UpsideDownBinaryTree(root):
    cur = TreeNode(root.val)
    parent = None
    parentRight = None
    while cur:
        #save left for next loop
        left = cur.left
        #update left
        cur.left = parentRight
        #save next parentRight
        parentRight = cur.right
        #update right
        cur.right = parent
        parent = cur
        #go to left, cause right is either leaf or empty
        cur = left 

    #leftmost is the new root
    return parent

Bottom-up

def UpsideDownBinaryTree(root):
    if not root:
        return None
    return self.dfsBottomUp(root, null)

def dfsBottomUp(p, parent):
    if not p:
        #left most node
        return parent
    root = dfsBottomUp(p.left, p)
    if not parent:
        #old root's parent
        p.left = None
    else:
        p.left = parent.right
    p.right = parent
    return root