156 Binary Tree Upside Down

来源：Leetcode

原帖：https://leetcode.com/problems/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

代码：

 /**   
  * Definition for binary tree  
  * struct TreeNode {  
  *   int val;  
  *   TreeNode *left;  
  *   TreeNode *right;  
  *   TreeNode(int x) : val(x), left(NULL), right(NULL) {}  
  * };  
  */  
   
 class Solution {  
 public:  
   TreeNode *upsideDownBinaryTree(TreeNode *root) {  
     if(!root || (!root->left && !root->right))   
       return root;  
     TreeNode * parent = upsideDownBinaryTree(root->left);  
     root->left->left = root->right;//because parameter could be NULL, so parent->left does not make sense.  
     root->left->right = root;   
     root->left = NULL;  
     root->right = NULL;  
     return parent;  
   }  
 };  
   
 class Solution {  
 public:  
   TreeNode* upsideDownBinaryTree(TreeNode* root) {  
     if (!root) return NULL;  
     TreeNode* p = root, *parent = NULL, *parentRight = NULL;  
     while (p) {  
       TreeNode* left = p->left;  
       p->left = parentRight;  
       parentRight = p->right;  
       p->right = parent;  
       parent = p;  
       p = left;  
     }  
     return parent;  
   }  
 };