PAT (Advanced Level) 1110. Complete Binary Tree (25)

时间:2020-12-12 08:49:04

判断一棵二叉树是否完全二叉树。

#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
#include<map>
#include<queue>
#include<stack>
#include<algorithm>
using namespace std; int n,root;
const int maxn=;
struct Node
{
int left;
int right;
int dep;
} s[maxn];
int flag[maxn];
vector<int>g[maxn];
int Max_dep=; void dfs(int x,int dep)
{
Max_dep=max(dep,Max_dep);
s[x].dep=dep;
g[dep].push_back(x); if(s[x].left!=-) dfs(s[x].left,dep+);
if(s[x].right!=-) dfs(s[x].right,dep+);
} int main()
{
memset(flag,,sizeof flag);
scanf("%d",&n);
for(int i=; i<n; i++)
{
char L[],R[];
scanf("%s%s",L,R);
if(L[]=='-') s[i].left=-;
else
{
int num=;
for(int k=; L[k]; k++) num=num*+L[k]-'';
s[i].left=num;
flag[num]=;
} if(R[]=='-') s[i].right=-;
else
{
int num=;
for(int k=; R[k]; k++) num=num*+R[k]-'';
s[i].right=num;
flag[num]=;
}
} for(int i=; i<n; i++)
if(flag[i]==) root=i; dfs(root,); if(Max_dep==)
{
printf("YES %d\n",g[Max_dep][g[Max_dep].size()-]);
}
else
{
bool fail=;
for(int i=; i<=Max_dep; i++)
{
if(i<Max_dep)
{
if(g[i].size()==(int)pow(2.0,i)) {}
else fail=;
}
else
{
for(int j=; j<g[i].size(); j=j+)
{
if(j+<g[i].size()&&j<g[i].size())
{
if(s[g[i-][j/]].left==g[i][j]&&s[g[i-][j/]].right==g[i][j+]) {}
else fail=;
}
else
{
if(s[g[i-][j/]].left==g[i][j]) {}
else fail=;
}
}
}
} if(fail==) printf("NO %d\n",root);
else printf("YES %d\n",g[Max_dep][g[Max_dep].size()-]);
}
return ;
}