力扣114，展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。展开后的单链表应该与二叉树 先序遍历 顺序相同。

递归写法（由于是递归所以不是空间复杂度$O(1)$的做法）

class Solution {
public:
struct TreeNode *pre = NULL;
void flatten(struct TreeNode* root) {
    if(root == NULL)return;
    flatten(root->right);
    flatten(root->left);
    root->right = pre;
    root->left = NULL;
    pre = root;
}
};

迭代写法（空间复杂度$O(1)$）

思路：curr = root，如果curr没有左子树，curr = curr->right，如果有左子树，根据先序遍历，右子树应该是左子树最右边的节点的右儿子，pre->right = curr->right，然后curr->right = curr->left，curr->left = NULL，curr = curr->right

class Solution {
public:
void flatten(struct TreeNode* root) {
    struct TreeNode *curr = root;
    while(curr != NULL){
        if(curr->left != NULL){
            struct TreeNode *pre = curr->left;
            while(pre->right != NULL){
                pre = pre->right;
            }
            pre->right = curr->right;
            curr->right = curr->left;
            curr->left = NULL;
        }
        curr = curr->right;
    }
}
};