TreeNode last = null;
public TreeNode upsideDownBinaryTree(TreeNode root) {
if(root==null) return null;
if(root.left==null) return root;
TreeNode left = upsideDownBinaryTree(root.left);
TreeNode right = upsideDownBinaryTree(root.right);
//Relink tree nodes
if(last==null) last = left;
last.left = root.right;
last.right = root;
//Remember to free the children nodes, otherwise MLE
root.left = null;
root.right = null;
last = root;
//The left most node is the new root so we return it
return left;
}
Simple Java recursive method use one auxiliary node


BTW, a more simple to understand but less efficient method: When you look at the reversed tree carefully, you'll find that the upsidedown tree is built from Post order traversal Therefore, you can post order traverse the tree and store them in an array, then build them from up to down.