649. 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.

Have you met this question in a real interview?  

Example

Example1
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

Example2
Given a binary tree {1,2,3,4}

    1
   / \
  2   3
 /
4

return the root of the binary tree {4,#,2,3,1}.

   4
    \
     2
     / \
  3   1

class Solution { public: /** * @param root: the root of binary tree * @return: new root */ TreeNode * upsideDownBinaryTree(TreeNode * root) { // write your code here //典型的recursion啊，但不太好想 if(root == NULL || (root->left == NULL && root->right == NULL)){ return root; } TreeNode* left = root->left; TreeNode* right = root->right; TreeNode *res = upsideDownBinaryTree(root->left); left->left = right; left->right = root; root->left = root->right = NULL; return res; } };