1、需求

我们知道，利用先序序列和中序序列可以唯一的确定一个二叉树，比如先序[1,2,4,5,3]和中序[4,2,5,1,3]可以构成二叉树：[1,2,3,4,5]。那思路落实到代码上应该如何写呢？

2、思路

想想我们是如何在脑海中把上述两个序列构建成二叉树的：

1. 先构造根节点：先序序列的第一个元素就是根节点的值；
2. 然后去中序序列去找这个根节点的位置，在中序序列中找到1，然后把中序序列划分成 [4,2,5] 和 [3] 两个序列，由于中序遍历的顺序是左根右，所以 [4,2,5] 是左子树的中序遍历结果，[3]是右子树的中序遍历结果。
3. 构造完根节点后，我们要去构建左子树和右子树。对于构建左子树和右子树，和构建根节点的逻辑是一样的。构建左子树时，左子树的先序序列是：[2,4,5]，左子树的中序序列是： [4,2,5] 。右子树的先序序列是[3],中序序列是[3]。

左子树的先序序列如何找呢？
先序遍历的顺序是根-左-右；中序遍历的顺序是左-根-右。所以先序遍历根左和中序遍历左根的结点个数是一样的。比如上述序列，我们找到左子树的中序遍历个数为[4,2,5]三个结点后，左子树的先序遍历个数应该是先序序列中根节点往后3个结点：[2,4,5]。

3、代码实现

我们只需要模拟上述的思路就行了，其实就是递归的实现。

//树结点结构
/**
struct node{
    node* left;
    node* right;
    int val;
};
*/
//递归建树
node* create(int pL,int pR,int mL,int mR,vector<int> &xianxu, vector<int>& zhongxu){
    if(pL>pR||mL>mR) return nullptr;

    node* root=new node;
    root->val=xianxu[pL];
    int k;
    //去中序序列中找该值
    for(k=mL;k<=mR;k++){
        if(zhongxu[k]==xianxu[pL]) break;
    }
    if(k>mR) return nullptr;
    int numLeft=k-mL;
    // 递归左子树
    root->left=create(pL+1,pL+numLeft,mL,k-1,xianxu, zhongxu);
    // 递归右子树
    root->right=create(pL+numLeft+1,pR,k+1,mR,xianxu,zhongxu);
        
    return root;
}

node* solve(vector<int>& xianxu, vector<int>& zhongxu) {

    node* root=create(0,xianxu.size()-1,0,zhongxu.size(),xianxu,zhongxu);
	return root;
}