要求展开为一个单链表，只使用 ->right ，顺序是先序

原地展开

如果节点存在左子树，则将左子树的右链插入到右子树； 否则遍历至右儿子

class Solution {
public:
    void flatten(TreeNode* root) {
        while (root) {
            auto p = root->left;
            if (p) {
                while (p->right) p = p->right;
                p->right = root->right;
                root->right = root->left;
                root->left = nullptr;
            }
            root = root->right;
        } 
    }
};

分别进行先序遍历和链表展开

class Solution {
public:
    vector<TreeNode*> vec;
    void flatten(TreeNode* root) {
        dfs(root);
        for (int i = 1; i < vec.size(); i ++) {
            TreeNode* pre = vec[i - 1];
            TreeNode* cur = vec[i];
            pre->left = nullptr;
            pre->right = cur;
        }
    }

    void dfs(TreeNode* root) {
        if (!root) return;
        vec.push_back(root);
        dfs(root->left);
        dfs(root->right);
    }
};