/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode UpsideDownBinaryTree(TreeNode root) {
        if(root == null)
            return null;
        ArrayList<ArrayList<Integer>> tmp = new ArrayList<ArrayList<Integer>>();
        helper(root, tmp);
        TreeNode newRoot = new TreeNode(tmp.get(tmp.size() - 1).get(0));
        tmp.remove(tmp.size() - 1);
        construct(newRoot, tmp);
        return newRoot;
    }

    public void helper(TreeNode root, ArrayList<ArrayList<Integer>> tmp)
    {
        if(root == null)
            return;
        ArrayList<Integer> cur = new ArrayList<Integer>();
        cur.add(root.val);
        if(root.right != null)
            cur.add(root.right.val);

        tmp.add(cur);

        helper(root.left, tmp);
    }

    public void construct(TreeNode newRoot, ArrayList<ArrayList<Integer>> tmp)
    {
        if(tmp.size() == 0)
            return;

        ArrayList<Integer> cur = tmp.get(tmp.size() - 1);
        if(cur.size() > 1)
            newRoot.left = new TreeNode(cur.get(1));
        newRoot.right = new TreeNode(cur.get(0));
        tmp.remove(tmp.size() - 1);

        construct(newRoot.right , tmp);
    }
}