Description:
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:
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
Link:
https://leetcode.com/problems/binary-tree-upside-down/description/
解题方法：
很恶心的一道题，之前花了大量时间在序列化和反序列化上来解这道题，后来发现其实不需要这样做。
这颗树是一颗左偏的树，而题目要求将这棵树上下颠倒并且变成右偏，那么在简单的数结构：
1
/ \
2 3
或者是
1
/ \
2 null
之中，上下颠倒代表着子节点之中一个要成为父节点。
因为结果是一颗右偏的数，所以原右孩子会成为之后的左孩子（因为原右孩子和变形之后的左孩子一样，不是叶子就是NULL）；而原左孩子则成为父节点；而原父节点毫无疑问只能成为右子树：
2
/ \
3 1
或者是
2
/ \
null 1
所以我们可以用迭代来完成这样的变形，只要记录下每层变形之后的父节点即可。
Time Complexity：
O(N)
完整代码：
TreeNode* upsideDownBinaryTree(TreeNode* root)
{
TreeNode* parent = root;
if(!parent)
return root;
TreeNode* left = parent->left;
TreeNode* right = parent->right;
parent->left = NULL;
parent->right = NULL;
//when left == NULL which means we touch the most left leaf
while(left)
{
TreeNode* nextLeft = left->left;
TreeNode* nextRight = left->right;
left->left = right;
left->right = parent;
//restore the parent node after one switch
parent = left;
left = nextLeft;
right = nextRight;
}
return parent;
}
