156. Binary Tree Upside Down

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.

For example:
Given a binary tree{1,2,3,4,5},
   1
   / \
  2  3
 / \
4  5
return the root of the binary tree[4,5,2,#,#,3,1].
    4
   / \
  5  2
 / \
3  1

刷晕了。。。。 1， 一个节点的左孩子等于他的兄弟节点， 右孩子等于父节点。
第一种迭代方法， 比较好容易理解还节省栈空间