先序遍历的第一个是root，第二个是左子节点或者右子节点。
后序遍历的最后一个是root，倒数第二个是左子节点或者右子节点。
倘若只知道先序和后序无法确定唯一一棵树，因为无法确认只有一个孩子节点的时候，这个孩子节点是左孩子还是右孩子
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int pre[50], post[50];
vector<int>in;
bool uni = true;
void getin(int preL, int preR, int postL, int postR)
{
if (preL == preR)
{
in.push_back(pre[preL]);
return;
}
if (pre[preL] == post[postR])
{
int i = preL + 1;
while (i <= preR&&pre[i] != post[postR - 1])i++;
if (i - preL > 1)getin(preL + 1, i - 1, postL, postL + (i - preL - 1) - 1);//左子树
else uni = false;
in.push_back(post[postR]);//根节点
getin(i, preR, postL + (i - preL - 1), postR - 1);//右子树
}
}
int main()
{
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++)scanf("%d", &pre[i]);
for (int i = 0; i < n; i++)scanf("%d", &post[i]);
getin(0, n - 1, 0, n - 1);
if (uni)printf("Yes\n");
else printf("No\n");
for (int i = 0; i < in.size(); i++)
{
printf("%d", in[i]);
if (i != in.size() - 1)printf(" ");
}
printf("\n");
return 0;
}
