Binary Tree Upside Down (LeetCode Tree)

Question: 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

Idea: Recursion. The new root is the left most node, which is also the new root of the flip of root's left substree. So we just need to keep track of the newRoot of flipping the left substrees and rotate the current level, left to root, root to right, right to left.

Time: O(n) Space: O(lgn) (each recursion call only pushes the left subtree to the stack)

Code:

 public class Solution {  
   public TreeNode UpsideDownBinaryTree(TreeNode root) {  
     if(root==null)  
       return null;  
     if(root.left==null&&root.right==null)  
       return root;  
     TreeNode newRoot=UpsideDownBinaryTree(root.left);  
     root.left.left=root.right;  
     root.left.right=root;  
     root.left=null;  
     root.right=null;  
     return newRoot;  
   }  
 }