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