AcWing 1600. 完全二叉树
原题链接
简单
作者:
leo123456
,
2020-08-22 18:38:17
,
所有人可见
,
阅读 570
#include<iostream>
#include<cstring>
using namespace std;
const int N=30;
int n;
int l[N],r[N];
int st[N];
int maxk,maxid;
void dfs(int u,int size)
{
// if(u==-1) return;
//
// if(size>maxk)
// {
// maxk=size;
// maxid=u;
// }
// dfs(l[u],size*2);
// dfs(r[u],size*2+1);
if(size>maxk)
{
maxk=size;
maxid=u;
}
if(l[u]!=-1) dfs(l[u],size*2);
if(r[u]!=-1) dfs(r[u],size*2+1);
}
int main()
{
memset(l,-1,sizeof l);
memset(r,-1,sizeof r);
cin>>n;
for(int i=0;i<n;i++)
{
string a,b;
cin>>a>>b;
if(a!="-") l[i]=stoi(a),st[stoi(a)]=true;
if(b!="-") r[i]=stoi(b),st[stoi(b)]=true;
}
int k=0;
while(st[k]) k++;
dfs(k,1);
if(maxk==n)
{
cout<<"YES"<<' '<<maxid<<endl;
}
else
{
cout<<"NO"<<' '<<k<<endl;
}
return 0;
}