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

confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

分析：

　　自底向上的右旋，用DFS搜到最左下角的节点，然后依次进行处理

代码：

class Solution {

private:

    TreeNode *newRoot;

public:

    void dfs(TreeNode* node) {

        if(!node->left) {

            newRoot = node;

            return;

        }

        dfs(node->left);

        node->left->left = node->right;

        node->left->right = node;

        return;

    }

    TreeNode* upsideDown(TreeNode* root) {

        if(root)

            dfs(root);

        return newRoot;

    }

};