二叉树展开为链表

投机取巧的方法是用一个vector保存结点再连接，但是还是不要这样做。

正常解法：

必要信息，链表尾部last指针

//         1
//        / \
//       2   5
//      / \    \
//     3   4    6 
//
//        1
//      /   \
//   left    right
//  left，2->3->4  链表尾部last
// right，5->6 链表尾部last

/**
 * 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:
    void flatten(TreeNode* root) {
        TreeNode* last = nullptr;
        preorder(root,last);
    }
    //              当前结点 ，   当前子树的先序遍历的最有一个结点
    void preorder(TreeNode* node,TreeNode* & last)
    {
        if(node == nullptr)
            return;
        //叶子结点
        if(node->left == nullptr && node->right==nullptr)
        {
            last = node;
            return;
        }
        //“先序”要处理的
        TreeNode* left = node->left;//备份左指针
        TreeNode* right = node->right;//备份右指针
        TreeNode* left_last = nullptr;//左子树的最后一个结点
        TreeNode* right_last = nullptr;//右子树的最后一个结点
        
        if(left)
        {
            preorder(left,left_last);
            //“中序”要处理的
            node->left = nullptr;
            node->right = left;
            last = left_last;
        }
        if(right)
        {
            preorder(right,right_last);
            //“后序”要处理的
            if(left_last)//有左子树
            {
                left_last->right = right;
            }
            last = right_last;
        }
    }
    
};