/**
 * 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:
    vector<int> res;
    void flatten(TreeNode* root) {
        if(root==NULL)
            return;
        inorder(root);
        // TreeNode* h = new TreeNode();
        // h->right = root;
        TreeNode* p = root;
        if(root->right) root->right->val = res[0];  
        // 对root根节点直接改变val值，如果改变指针，导致函数返回值root会改变。
        for(int i = 1; i < res.size(); i++){
            TreeNode* temp = new TreeNode(res[i]);
            p->right = temp;
            p->left = NULL;
            p = temp;
        }

    }
    void inorder(TreeNode* root){
        if(root == NULL)
            return;
        res.push_back(root->val);
        if(root->left)
            inorder(root->left);
  
        if(root->right)
            inorder(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) {
        // if(root==NULL)
        //     return;
        while(root!=NULL){
            if(root->left==NULL)
                root = root->right;
           else{
            cout<<"root->val:"<<root->val<<endl;
            TreeNode* temp = root->left;
            while(temp->right!=NULL){
                temp = temp->right;
                }
            temp->right = root->right;
            root->right = root->left;
            root->left = NULL;
            root = root->right;
            }
        }
    }
};