LeetCode - Binary Tree Upside Down

BinaryTreeUpsideDown.java

// 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  

TreeNode new_root = null;
public TreeNode upsideDownBinaryTree(TreeNode root) {
    helper(root);
    return new_root;
}

private TreeNode helper(TreeNode root){
    if(root == null) return root;
    TreeNode left = root.left, right = root.right;
    root.left = null;
    root.right = null;
    TreeNode pre = helper(left);
    if(new_root == null){
        new_root = root;
        pre = root;
    } else {
        pre.left = right;
        pre.right = root;
    }
    return root;
}

// solution 2
public TreeNode upsideDownBinaryTree(TreeNode root) {
    if (root == null || 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;
}

// solution 3
public TreeNode upsideDownBinaryTree(TreeNode root) {
    if(root == null) return root;
    TreeNode cur = root;
    TreeNode pre = null;
    TreeNode next = null;
    TreeNode temp = null;
    while(cur != null){
        next = cur.left;
        cur.left = temp;
        temp = cur.right;
        cur.right = pre;
        pre = cur;
        cur = next;
    }
    return pre;
}