题目链接：题目详情 - 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;
}