class Solution {

public:

    void helper(TreeNode* cur, TreeNode*& tail){

        //a(tail)

        //lk("root",tail)

        //a(cur)

        //lk("root",cur)

        //dsp

        tail=cur;

        TreeNode* right=cur->right;

        //a(right)

        //lk("root",right)

        if(cur->left){

            TreeNode *leftTail=NULL;

            helper(cur->left, leftTail);

            cur->right=cur->left;

            cur->left=NULL;

            tail=leftTail;

            //dsp

        }

        if(right){

            TreeNode *rightTail=NULL;

            helper(right, rightTail);

            tail->right=right;

            tail=rightTail;

            //dsp

        }

    }

    void flatten(TreeNode* root) {

        if(!root)

            return;

        //ahd(root)

        TreeNode *tail=NULL;

        helper(root, tail);

    }

};