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

1 /**  2  * Definition for a binary tree node.  3  * public class TreeNode {  4  *     public int val;  5  *     public TreeNode left;  6  *     public TreeNode right;  7  *     public TreeNode(int x) { val = x; }  8  * }  9  */ 10  11 // iterative solution with O(1) space 12 public class Solution { 13     public TreeNode UpsideDownBinaryTree(TreeNode root) { 14         if (root == null) return null; 15          16         TreeNode cur = root, parent = null, parentRight = null; 17          18         while (cur != null) 19         { 20             TreeNode curLeft = cur.left, curRight = cur.right; 21              22             cur.right = parent; 23             cur.left = parentRight; 24              25             parent = cur; 26             parentRight = curRight; 27             cur = curLeft; 28         } 29          30         return parent; 31     }  32 } 33  34 // recurive solution 35 public class Solution1 { 36     public TreeNode UpsideDownBinaryTree(TreeNode root) { 37         if (root == null) return null; 38         var newRoot = new TreeNode[1]; 39          40         DFS(root, newRoot); 41          42         return newRoot[0]; 43     }  44      45     private TreeNode DFS(TreeNode node, TreeNode[] newRoot) 46     { 47         if (node.left == null) 48         { 49             newRoot[0] = node; 50             return node; 51         } 52          53         var root = DFS(node.left, newRoot); 54          55         node.left = null; 56         var right = node.right; 57         node.right = null; 58          59         root.left = right; 60         root.right = node; 61          62         return node; 63     } 64 } 65  66 // cleaner recurive solution 67 public class Solution2 { 68     public TreeNode UpsideDownBinaryTree(TreeNode root) { 69         if (root == null || root.left == null) return root; 70          71         var newRoot = UpsideDownBinaryTree(root.left); 72          73         root.left.left = root.right; 74         root.left.right = root; 75          76         root.left = null; 77         root.right = null; 78          79         return newRoot; 80     }      81 } 82  83 // iterative solution 84 public class Solution3 { 85     public TreeNode UpsideDownBinaryTree(TreeNode root) { 86         if (root == null) return null; 87          88         var stack = new Stack
     
      (); 89          90         while (root != null) 91         { 92             stack.Push(root); 93             root = root.left; 94             stack.Peek().left = null; 95         } 96          97         var newRoot = stack.Pop(); 98         var cur = newRoot; 99         100         while (stack.Count > 0)101         {102             var top = stack.Pop();103             cur.left = top.right;104             cur.right = top;105             top.right = null;106             cur = top;107         }108         109         return newRoot;110     } 111 }
     

 

1 /** 2  * Definition for a binary tree node. 3  * public class TreeNode { 4  *     public int val; 5  *     public TreeNode left; 6  *     public TreeNode right; 7  *     public TreeNode(int x) { val = x; } 8  * } 9  */10 11 // iterative solution with O(1) space12 public class Solution {13     public TreeNode UpsideDownBinaryTree(TreeNode root) {14         if (root == null) return null;15         16         TreeNode cur = root.left, parent = root, parentRight = root.right;17         root.left = null;18         root.right = null;19         20         while (cur != null)21         {22             TreeNode curLeft = cur.left, curRight = cur.right;23             24             cur.right = parent;25             cur.left = parentRight;26             27             parent = cur;28             parentRight = curRight;29             cur = curLeft;30         }31         32         return parent;33     } 34 }35 36 // recurive solution37 public class Solution1 {38     public TreeNode UpsideDownBinaryTree(TreeNode root) {39         if (root == null) return null;40         var newRoot = new TreeNode[1];41         42         DFS(root, newRoot);43         44         return newRoot[0];45     } 46     47     private TreeNode DFS(TreeNode node, TreeNode[] newRoot)48     {49         if (node.left == null)50         {51             newRoot[0] = node;52             return node;53         }54         55         var root = DFS(node.left, newRoot);56         57         node.left = null;58         var right = node.right;59         node.right = null;60         61         root.left = right;62         root.right = node;63         64         return node;65     }66 }67 68 // iterative solution69 public class Solution2 {70     public TreeNode UpsideDownBinaryTree(TreeNode root) {71         if (root == null) return null;72         73         var stack = new Stack
     
      ();74         75         while (root != null)76         {77             stack.Push(root);78             root = root.left;79             stack.Peek().left = null;80         }81         82         var newRoot = stack.Pop();83         var cur = newRoot;84         85         while (stack.Count > 0)86         {87             var top = stack.Pop();88             cur.left = top.right;89             cur.right = top;90             top.right = null;91             cur = top;92         }93         94         return newRoot;95     } 96 }