二叉树转链表

给定一个二叉树，将该二叉树 就地(in-place)转换为单链表。单链表中节点顺序 为二叉树前序遍历顺序。(不额外开辟存储空间)
LeetCode 114. Flatten Binary Tree to Linked List

struct TreeNode{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) :
        val(x), left(NULL), right(NULL){} 
};//但链表仍使用该数据结构，即left =NULL，right = next；
class Solution{
public:
    void flatten(TreeNode *root){
    }
};

前序遍历二叉树，将节点指针 push进入vector，顺序遍历vector中的节点，链接相邻 两节点，形成链单链表。(投机取巧) 该方法虽然可通过题目，但不满足就地(in-place)转换的条件。 若就地(in-place)转换应该如何做?

方法1 使用 vector

#include<vector>
public:
    void flatten(TreeNode *root){
        std::vector<TreeNode *> node_vec;
        preorder(root, node_vec);
        for(int i =1; i< node_vec.size(); i++){
            node_vec[i-1]->left = NULL;
            node_vac[i-1]->right = node_vec[i];
            
        }
private:
      void preorder(TreeNode *node, std::vector<TreeNode*> &node_vec){
      if(!node){
          return;
      }
      node_vec.push_back(node);
      preorder(node->left, node_vec);
      preorder(node->right,node_vec);
      }
    }

方法二：算法设计
将node指向的节点转为单链表，即将左子树left转为单链表，记录左子树最后一个节点 指针 left_last，将右子树right转换为单链表，记录右子树最后一个节点指针right_last，最终node 节点与左子树相连，left_last与right相连，函数要将right_last指针传出。

备份node->left指针、node->right指针，存储至left、right，设置存储左子树最后一个节点 指针left_last，存储右子树最后一个节点指针right_last，存储node节点为根的子树最后一个节点指针last。
如果左指针不空: 递归将左子树 拉直，并计算 left_last，node->left附空， node->right赋值 left，last赋值为 left_last;
如果右指针不空: 递归将右子树 拉直，并计算 right_last，左子树最后一个节点与右子树 相连，last赋值为 right_last。

class Solution{
public:
    void flatten(TreeNode *root){
        TreeNode * last = NULL;
        preorder(root,last);
    }
private:
    void preorder(TreeNode *node,TreeNode *&last){
         if(!node){
          return;
          }
          if(!node->left && !node->right){
          last = node;
          return;
          }
          TreeNode *left = node->left;//备份左右指针
          TreeNode *right = node->right;
          TreeNode *left_last = NULL;
          TreeNode *right_last = NULL;//左右子树最后一个节点
          if(left){
              preorder(left, left_last);// 
              node->left = NULL;
              node->right = left;
              last = left_last;
          }
          if(right){
              preorder(right, right_last);
              if(left_last){
                  left_last->right = right;
              }
              last = right_last;
          }
    }
};