题意

• 给定一个树的先序遍历和后序遍历，求他的中序遍历，无法确定的时候，认为是左子树

思路

• 若没有规定左子树，则给定先序和后序是无法确定的，但规定后即可
• 对于先序遍历，第一个点总是当前的根，第二个点总是当前左子树的根
• 对于后序遍历，找到由先序确定的左子树的根的位置，由后续的头到该位置为左子树，由该位置加一到倒数第二位是右子树
• 在划分完后序里的左右子树后，可以确定两个子树的长度，因此可以找到先序遍历中左子树的屁股，左子树的屁股加一到先序序列的最后就是右子树
• 找到以后按照递归左子树-根-递归右子树的顺序存入中序序列中

AC代码

#include<bits/stdc++.h>
using namespace std;
vector<int> mid;
void deal(int l1, int r1, int l2, int r2, vector<int> &p, vector<int> &b){
	if(l1>r1)return;
	//对于一个没有右子树的序列，如先序AB，后序BA
	//这时候在后序中左子树根加一就不是右子树了，同时根减一也指向了左子树而非右子树
	//发生了错位，所以非法情况存在，需要处理
	if(l1==r1){mid.push_back(p[l1]);return ;}
	int x=p[l1+1];
	int pos=-1;//左子树的根的位置
	for(int i=l2;i<=r2;i++) if(b[i]==x)pos=i;
	deal( l1+1, l1+1+pos-l2, l2, pos, p, b);
	//递归处理左子树，通过在后序遍历中的长度确认在先序遍历中的长度
	mid.push_back(p[l1]);//根
	deal ( l1+1+pos-l2+1, r1, pos+1, r2-1, p, b);//递归处理右子树，
}
int main(){
	int n;
	scanf ("%d", &n);
	vector<int>pre(202020),back(202020);
	for(int i=0;i<n;i++)scanf("%d",&pre[i]);
	for(int i=0;i<n;i++)scanf("%d",&back[i]);
	deal(0, n-1, 0, n-1, pre, back );
	for(auto i : mid ){
		printf( "%d ", i);
	}
}

注意：

• 边界情况除了相等还要考虑有没有可能左界跑到右界的右边的非法情况