递归实现:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    void flatten(TreeNode* root) {
        if(!root) return;
        
        flatten(root->left);
        flatten(root->right);
        
        if(root->left != nullptr)
        {
            //save the origin root->right
            TreeNode* right = root->right;
            
            //change left to right
            root->right = root->left;
            root->left = nullptr;
            
            //find the rightest
            while(root->right)
                root = root->right;

            root->right = right;
        }
    }
};

递归真的是巧妙，首先这类递归问题，可以先构建一个最小问题场景，然后按照最小问题场景编写 if(root->left != nullptr)部分代码，那么如果问题规模大的话如何处理呢？这里就是这类递归问题的精髓了，直接调用 flatten(root->left); flatten(root->right);递归的处理问题，实际上执行的时候会不断的递归向下直到遇到最小子问题，然后处理完子问题再递归层层往上。
迭代实现(同样非常巧妙，细细体会)：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    void flatten(TreeNode* root) {
        TreeNode* now = root;
        while(now){
            if(now->left)
            {
                TreeNode* pre = now->left;
                while(pre->right)
                    pre = pre->right;
                
                pre->right = now->right;
                now->right = now->left;
                now->left = nullptr;
            }
            now = now->right;
        }
    }
};