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},

return the root of the binary tree [4,5,2,#,#,3,1].

将left node 入stack，然后将每个原来的left node的 left = parent.right, right = parent. (从下往上做)

 1 /**
 2  * Definition for binary tree
 3  * public class TreeNode {
 4  *     int val;
 5  *     TreeNode left;
 6  *     TreeNode right;
 7  *     TreeNode(int x) { val = x; }
 8  * }
 9  */
10 public class Solution {
11     public TreeNode UpsideDownBinaryTree(TreeNode root) {
12         if(root == null) return root;
13         LinkedList<TreeNode> ll = new LinkedList<TreeNode> ();
14         ll.push(root);
15         while(root.left != null){
16             ll.push(root.left);
17             root = root.left;
18         }
19         while(!ll.isEmpty()){
20             TreeNode tmp = ll.pop();
21             tmp.right = ll.peek();
22             tmp.left = ll.peek() == null ? null : ll.peek().right;
23         }
24         return root;
25     }
26 }

从上往下做：

 1 public class Solution {
 2     public TreeNode UpsideDownBinaryTree(TreeNode root) {
 3         if(root == null) return root;
 4         TreeNode cur = root, last = null, lastRight = null;
 5         while(cur != null){
 6             TreeNode tmp = cur.left;
 7             cur.left = lastRight;
 8             lastRight = cur.right;
 9             cur.right = last;
10             last = cur;
11             cur = tmp;
12         }
13         return last;
14     }
15 }