114. 二叉树展开为链表

给定一个二叉树，原地将它展开为链表。

例如，给定二叉树

1

/
2 5
/ \
3 4 6
将其展开为：

1

2

3

4

5

6

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    struct ptr
    {
        TreeNode* start;
        TreeNode* end;
        ptr(){start=NULL;end=NULL;}
    };
    ptr dfs(TreeNode* root)
    {
        ptr t;
        if(root==NULL) return t;
        ptr t1=dfs(root->left);
        ptr t2=dfs(root->right);
        root->left=NULL;
        t.start=root;
        t.end=root;
        if(t1.start!=NULL)
        {
             root->right=t1.start;
             root=t1.end;
             t.end=t1.end;
        }
        if(t2.start!=NULL)
        {
            root->right=t2.start;
            t.end=t2.end;
        }
         return t;
        
    }
    void flatten(TreeNode* root) {
        ptr t=dfs(root);
        
    }
};