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/
解題方法：
很惡心的一道題，之前花了大量時(shí)間在序列化和反序列化上來(lái)解這道題，后來(lái)發(fā)現(xiàn)其實(shí)不需要這樣做悄但。
這顆樹是一顆左偏的樹粹舵，而題目要求將這棵樹上下顛倒并且變成右偏伞梯，那么在簡(jiǎn)單的數(shù)結(jié)構(gòu)：
1
/ \
2 3
或者是
1
/ \
2 null
之中奶稠，上下顛倒代表著子節(jié)點(diǎn)之中一個(gè)要成為父節(jié)點(diǎn)赡盘。
因?yàn)榻Y(jié)果是一顆右偏的數(shù)爪膊，所以原右孩子會(huì)成為之后的左孩子（因?yàn)樵液⒆雍妥冃沃蟮淖蠛⒆右粯尤ㄎ颍皇侨~子就是NULL）；而原左孩子則成為父節(jié)點(diǎn)推盛；而原父節(jié)點(diǎn)毫無(wú)疑問(wèn)只能成為右子樹：
2
/ \
3 1
或者是
2
/ \
null 1
所以我們可以用迭代來(lái)完成這樣的變形峦阁，只要記錄下每層變形之后的父節(jié)點(diǎn)即可。
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;
}
