156. Binary Tree Upside Down

Problem:

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  

Analysis:
4/24/2018 update:
Approach 1: Recursive
The goal is to return the left most node before restructure the tree. So we have to get that node before we do anything about changing tree structure. Assign root's left and right to null to keep the tree clean.

class Solution {
    public TreeNode upsideDownBinaryTree(TreeNode root) {
        if (root == null || root.left == 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;
    }
}

Approach 2: Iterative
Image steal from leetcode discussion.

cur.left and cur.right will be overwritten, so we need to cache them with next and temp.
--------------------------------------------------------------------------------------------------------------------------
From top down, we want to do
1. cur.left = parent.right
2. cur.right = parent

My original approach is:

 class Solution {  
   public TreeNode upsideDownBinaryTree(TreeNode root) {  
     if (root == null) return null;  
     TreeNode prev = root;  
     TreeNode cur = root.left;  
     while (cur != null) {  
       cur.left = prev.right;  
       cur.right = prev;  
       prev = cur;  
       cur = cur.left;  
     }  
     return prev;  
   }  
 }  

the root's left and right have not been taken care of. They should be null.

Solution:

 class Solution {  
   public TreeNode upsideDownBinaryTree(TreeNode root) {  
       TreeNode curr = root;  
       TreeNode next = null;  
       TreeNode temp = null;  
       TreeNode prev = null;  
       while(curr != null) {  
         next = curr.left;  
         // swapping nodes now, need temp to keep the previous right child  
         curr.left = temp;  
         temp = curr.right;  
         curr.right = prev;  
         prev = curr;  
         curr = next;  
       }  
       return prev;  
   }  
 }