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

confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

Recursive solution:
The recursive solution could be bottom-up. Note that we need a parent node to save the node's parent. Also we use the return value just to store the new node. 

这个题的关键是反转以后的binary tree 的 root 是以前二叉树的 最左边的 leaf node. 利用这个性质，我们先一路走到最左边的那个leaf node, 并且记录一下当前节点和之前的parent node。找到这个节点以后，利用返回值一直把这个点传回来。在back tracking 的过程中，当前root 的 left child 是 parent.right. (注意要判断parent 是否为null)。如果parent == null, root.left = null; 如果没有这一句，树里面就有一个环！！root.right = parent

这个题的思路比较类似reverse linked list in recursive way. 

Code (Java):

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode upsideDownBinaryTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        
        return upsideDownBinaryTreeHelper(root, null);
    }
    
    private TreeNode upsideDownBinaryTreeHelper(TreeNode root, TreeNode parent) {
        if (root == null) {
            return parent;
        }
        
        TreeNode newNode = upsideDownBinaryTreeHelper(root.left, root);
        
        root.left = parent == null ? null : parent.right;
        root.right = parent;
        
        return newNode;
    }
}

Iterative solution:
这个属于自顶向下的方法。需要注意的是在向下走的过程中parent 其实已经被更新了，所以p.left 就不能指向parent.right, 因为 parent.right 已经在向下遍历的过程里面丢了！所以需要保存这个parent.right 这个node. 

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode upsideDownBinaryTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        
        TreeNode parent = null;
        TreeNode parentRightChild = null;
        TreeNode p = root;
        
        while (p != null) {
            TreeNode next = p.left;
            p.left = parentRightChild;
            parentRightChild = p.right;
            
            p.right = parent;
            
            parent = p;
            p = next;
        }
        
        return parent;
    }
}