题目链接：题目详情 - 7-16 Pseudo-completeness (pintia.cn)
样例1输入：
7
4 2 5 1 6 3 7
1 2 4 5 3 6 7
样例1输出：
1
4 5 2 6 7 3 1
样例2输入：
10
8 4 9 2 10 5 1 6 3 7
1 2 4 8 9 5 10 3 6 7
样例2输出：
2
8 9 4 10 5 2 6 7 3 1
样例3输入：
10
8 4 2 5 11 1 6 3 14 7
1 2 4 8 5 11 3 6 7 14
样例3输出：
3
8 4 11 5 2 6 14 7 3 1
题目翻译：
在计算机科学中，“完美二叉树”（perfect binary tree）是指，二叉树的所有非叶结点都有两个孩子结点，且所有叶结点的深度相同。“完全二叉树”（complete binary tree）是指，二叉树中除了最后一层外，其他层都被填满，并且最后一层的所有结点都尽可能地靠左边。若一棵二叉树，最后一层被移除后就变成“完美二叉树”，则这棵二叉树就是“伪完全二叉树”（pseudo-complete binary tree）。
给定一棵二叉树的中序和前序遍历序列，请你判断这棵树的类型，并输出它的后序遍历序列。
输入格式：
每个输入文件包含一个测试用例。第一行是正整数N（≤2000），表示树中结点数量。接下来两行分别是中序和前序遍历序列。题目保证结点值各不相同且均在int型范围。输入的数由空格间隔。
输出格式：
第一行输出所输入树的类型：1为完美二叉树，2为完全二叉树（但不是类型1），3为伪完全二叉树（但不是类型1和2），0为其他类型的二叉树。第二行输出后序遍历序列，以空格间隔，且行首和行末没有多余的空格。
分析：这个题目的第一步还是很显然的，就是根据二叉树的前序遍历和中序遍历确定树的结构，至于最后输出树的后续遍历也是很简单的。下面主要分析一下如何判断是哪一种类型。
我们可以按照完美二叉树的标准来对树进行编号，然后我们可以遍历一遍树，记录所有节点中的最大编号，如果最大编号不等于节点个数n，那么他一定不可能是完美二叉树或者完全二叉树，等于n的话一定是完全二叉树，而完美二叉树的节点个数一定是2的某幂次-1，根据这个再做进一步判断即可。我们在搜索树的时候可以加入一个参数记录当前节点的深度，首先如果要是该树属于三种类型中的一个，那么层数显然是(int)log2(n)+1，这是显然的，那么如果某个节点的层数大于这个值，那么显然是不属于三种类型的，可以直接返回0.最后我们就需要判断一下该树是否是伪二叉树，这个的话根据定义判断即可，就是去掉最后一层节点后判断剩余节点是否是完美二叉树即可，那么就需要我们统计一下最后一层的节点个数，完美二叉树的一个特征就是节点数等于2的某幂次-1，我们利用这个特征即可判断该树是否是伪完全二叉树。最后按照题意依次输出即可。
细节见代码：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<map>
#include<queue>
#include<vector>
#include<cmath>
using namespace std;
const int N=1e5+10;
int a[N],b[N],l[N],r[N],mp[N];
int c[N],idx;//用来存储后序遍历序列
vector<int> alls;
int find(int x)
{
return lower_bound(alls.begin(),alls.end(),x)-alls.begin()+1;
}
int build(int l1,int r1,int l2,int r2)//建树
{
if(l1==r1) return a[l1];
if(l1+1+(mp[a[l1]]-1-l2)>=l1+1)
l[a[l1]]=build(l1+1,l1+1+(mp[a[l1]]-1-l2),l2,mp[a[l1]]-1);
if(r1>=l1+1+(mp[a[l1]]-1-l2)+1)
r[a[l1]]=build(l1+1+(mp[a[l1]]-1-l2)+1,r1,mp[a[l1]]+1,r2);
return a[l1];
}
bool flag1=true,flag2=true,flag3=true;
int mxid=1,n;
int cnt;//统计最后一层节点的个数
void check(int x,int h,int id)//判断树的类型
{
mxid=max(mxid,id);
if(h>(int)log2(n)+1)
{
flag1=false;
flag2=false;
flag3=false;
return ;//已经确定类型是0了，继续搜索已经没有意义了
}
if(h==(int)log2(n)+1) cnt++;
if(l[x]&&r[x])//左右子树都有
{
check(l[x],h+1,id<<1);
check(r[x],h+1,id<<1|1);
}
else if(l[x])//只有左子树
check(l[x],h+1,id<<1);
else if(r[x])
check(r[x],h+1,id<<1|1);
return ;
}
void show(int x)//输出后序遍历
{
if(l[x]) show(l[x]);
if(r[x]) show(r[x]);
c[++idx]=x;
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
scanf("%d",&b[i]),alls.push_back(b[i]);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
sort(alls.begin(),alls.end());//离散化
alls.erase(unique(alls.begin(),alls.end()),alls.end());
for(int i=1;i<=n;i++)
{
a[i]=find(a[i]);
b[i]=find(b[i]);
mp[b[i]]=i;
}
int root=build(1,n,1,n);
check(root,1,1);
int t=1;
while(t<=n) t<<=1;
if(n+1!=t) flag1=false;//完全二叉树的结点个数一定是2的幂次-1
if(mxid!=n) flag1=flag2=false;
if(n-cnt!=(t>>1)-1) flag3=false;
if(flag1) puts("1");
else if(flag2) puts("2");
else if(flag3) puts("3");
else puts("0");
show(root);
for(int i=1;i<=n;i++)
{
printf("%d",alls[c[i]-1]);
if(i!=n) printf(" ");
}
return 0;
}
