LeetCode 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
比较抽象，需要理解upside down的含义。变化为：上往下的树=>左往右的树。从根节点开始遍历每个左儿子node（包含起始的root），node的右儿子变为其parent，左儿子变为其右儿子，node=left循环遍历下一个左儿子，直到左儿子为空。
upside down BT.PNG
public class Solution {
public TreeNode upsideDownBinaryTree(TreeNode root) {
TreeNode node = root, parent = null, right = null;
while (node != null) {
TreeNode left = node.left;
node.left = right;
right = node.right;
node.right = parent;
parent = node;
node = left;
}
return parent;
}
}
