由樹前序周遊、中序周遊構造樹 c++

前序周遊 中左右（先通路根節點）

中序周遊 左中右（中間通路根節點）

前序周遊序列{1,2,4,7,3,5,6,8}

中序周遊序列{4,7,2,1,5,3,8,6}

分析： 前序周遊是中左右，是以第一個一定是根節點的值，根據這個值可以在中序周遊中找到左右子樹的分割

左子樹的中序周遊 -> 4,7,2       1       5,3,8,6  <-右子樹的中序周遊

左子樹的先序周遊->  2,4,7                3,5,6,8  <-右子樹的先序周遊

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
        if(pre.size()==0)return NULL;
        TreeNode* root=new TreeNode(pre[0]);
        //分
        int which=-1;
        int len=vin.size();
        while(vin[++which]!=pre[0]);
        //  pre  1-which  which+1 len-1
        //  vin  0-which-1  which+1 len-1
        
        vector<int> pre1(pre.begin()+1,pre.begin()+which+1);
        vector<int> pre2(pre.begin()+which+1,pre.end());
        vector<int> vin1(vin.begin(),vin.begin()+which);
        vector<int> vin2(vin.begin()+which+1,vin.end());
        root->left=reConstructBinaryTree(pre1,vin1);
        root->right=reConstructBinaryTree(pre2,vin2);
        return root;
    }
};