共计 959 个字符，预计需要花费 3 分钟才能阅读完成。
之前仅仅接触过如何通过二叉树的中序 + 先序 / 后序序列生成唯一二叉树，这一次见到了这个新的题型；
这里先梳理一个概念，之所以会生成树不唯一，一定是有一个叶子，无论其在父节点的左右子节点，都可能生成相同的先序和后序遍历序列；
所以这个时候，思路就很清晰，我们判别一个序列是否唯一，条件就是是否有一个节点只有一个子节点；
大致的序列分割和先序和后续相同，这个后面专门开一个 blog 进行总结；
#include<iostream>
#include<stdlib.h>
#include<stdio.h>
#include<vector>
#include<set>
#include<algorithm>
using namespace std;
using std::vector;
using std::set;
vector<int>in,pre,post;
bool uniq=true;
void chargement(int prl,int prr,int pol,int por){
if(prl==prr){
in.push_back(pre[prl]);
return ;
}
if(pre[prl]==post[por]){
int i=prl+1;
while(i<=prr&&pre[i]!=post[por-1])
i++;
if(i-prl>1)
chargement(prl+1,i-1,pol,pol+(i-prl-1)-1);
else
uniq=false;
in.push_back(post[por]);
chargement(i,prr,pol+(i-prl-1),por-1);
}
}
int main(){
int n;
scanf(“%d”,&n);
pre.resize(n);
post.resize(n);
for(int i=0;i<n;i++)
scanf(“%d”,&pre[i]);
for(int i=0;i<n;i++)
scanf(“%d”,&post[i]);
chargement(0,n-1,0,n-1);
printf(“%s\n%d”, uniq == true ? “Yes” : “No”, in[0]);
for (int i = 1; i < in.size(); i++)
printf(” %d”, in[i]);
printf(“\n”);
system(“pause”);
return 0;
}
