Flatten Binary Tree to Linked List--LeetCode

题目：

Given a binary tree, flatten it to a linked list in-place.

For example,
Given

The flattened tree should look like:

思路：从遍历的顺序上是前序遍历的结果，那么使用前序遍历，在前序遍历的过程中改变树结构，对于当前节点，是作为一个新的链表的头部，然后递归调用初始化左子树，递归调用右子树，为了能够连接，还得记住链表的尾部，当前节点的右子树是左子树改造后的链表的头节点，左子树的尾部后端是右子树的头部。

在实现的时候需要注意，最后的连接需要注意查看是否为空的操作。

void helper_list(BinTree*& root,BinTree*& head,BinTree*& tail)
{
    if(root == NULL ||(root->right == NULL && root->left == NULL))
    {
        head = root;
        tail = root;
        return ;
    }
     head = root;
    BinTree* left_head = root->left;
    head->left = NULL;
    BinTree* left_tail = NULL;
    BinTree* right_head = root->right;
    BinTree* right_tail = NULL;
    helper_list(left_head,left_head,left_tail);
    helper_list(right_head,right_head,right_tail);
    if(left_head != NULL)
        head->right = left_head;
    else
        head->right = right_head;
    if(left_tail != NULL)
        left_tail->right = right_head;
    if(right_tail != NULL)
        tail = right_tail;
    else
        tail = left_tail;
}
BinTree* LinkedList(BinTree* root)
{
    if(root == NULL)
        return NULL;
    BinTree * head=NULL,*tail=NULL;
    helper_list(root,head,tail);
    return head;
}