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;
    }
}