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

Left child as root, root as right-most child's right child, right child as right-most child's left child.

    public TreeNode upsideDownBinaryTree(TreeNode root) {
        if(root == null) return null;
        else if(root.left == null && root.right == null) return root;

        TreeNode leftNode = upsideDownBinaryTree(root.left), rightNode = root.right, currNode = leftNode;
        root.left = null;
        root.right = null;
        if(currNode != null){
            while(currNode.right != null)
                currNode = currNode.right;
            currNode.right = root;
            currNode.left = rightNode; 
            return leftNode;
        }
        else return root;
    }

    public TreeNode upsideDownBinaryTree(TreeNode root) {

        if(root == null || (root.left == null && root.right == null)) return root;

        TreeNode left = upsideDownBinaryTree(root.left), t = left;

        while(t.right != null)
            t = t.right;

        t.left = root.right;
        root.right = null;

        t.right = root;
        root.left = null;

        return left;
    }

iterative way:

def upsideDownBinaryTree(self,root):
    if not root: return root
    prev,prev_right = None,None
    while root:
        root.left,root.right,prev,prev_right,root = prev_right,prev,root,root.right,root.left
    return prev