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

 
class Solution {
public:
    TreeNode * newRoot=NULL;
    bool found=false;
    TreeNode *upsideDownBinaryTree(TreeNode *root) {
        if(root==NULL) return NULL;
        if(root->left==NULL) return root;
        recursive(root);
        return newRoot;
    }
    void recursive(TreeNode *root){
        if(root->left==NULL) return;
        recursive(root->left);
        if(root->left->left==NULL){
            if(!found){newRoot=root->left; found=true;}
            root->left->left=root->right;
            root->right=NULL;
            root->left->right=root;   
            root->left=NULL;
        }
    }
};

 
public class Solution {
    public TreeNode UpsideDownBinaryTree(TreeNode root) {
        TreeNode p = root, parent = null, parentRight = null;
        while (p!=null) {
            TreeNode left = p.left;
            p.left = parentRight;
            parentRight = p.right;
            p.right ＝ parent;
            parent = p;
            p = left;
        }
        return parent;
    }
}

 
/** 
 * Definition for binary tree 
 * struct TreeNode { 
 *     int val; 
 *     TreeNode *left; 
 *     TreeNode *right; 
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} 
 * }; 
 */ 
class Solution { 
public: 
    TreeNode *upsideDownBinaryTree(TreeNode *root) { 
        //using a dummy node to help to store the new tree       
        TreeNode dummy(0); 
        TreeNode *head =  &dummy, *left=NULL, *right=NULL; 


        while ( root!=NULL ) { 
            //find the right & left 
            left = root->right; 
            right = root; 
             
            //move root the next 
            root = root->left; 
             
            //replace the right with current root 
            right->left = head->left; 
            right->right = head->right; 
             
            //move the dummy to the root 
            dummy.right = right; 
            dummy.left = left; 
             
            //reset the head to the root 
            head = &dummy; 
     
        } 
         
        return head->right; 
    } 
};