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

S: recursion O(N)

利用原来的left，right关系进行操作，每一步的返回值都一样即为原树最左节点

    TreeNode* upsideDownBinaryTree(TreeNode* root) {
        if (!root || !root->left) {
            return root;
        }
        TreeNode* newRoot = upsideDownBinaryTree(root->left);
        root->left->right = root;  //利用原来的left，right关系得到root的father,即为原来的root->left
        root->left->left = root->right;
        root->left = NULL;
        root->right = NULL;
        return newRoot;
    }