【1110】Complete Binary Tree (25分)【完全二叉树】

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#include<algorithm>  
#include<map>
#include<vector>
#include<queue> 
#include<string>
using namespace std;  
//如果为完全二叉树，maxn才能与n相等
struct node{
  int l,r;
}a[100];
int maxn=-1,ans;
void dfs(int root,int index){//判断树是否为完全二叉树
  if(index>maxn){//如果为完全二叉树，maxn才能与n相等
    maxn=index;
    ans=root;
  }
  if(a[root].l!=-1)  dfs(a[root].l,index*2);
  if(a[root].r!=-1)  dfs(a[root].r,index*2+1);
}
int main(){   
  int n,root=0,have[100]={0};
  cin>>n;//结点总数n
  for(int i=0;i<n;i++){//构建树，查找根结点
    string l,r;
    cin>>l>>r;
    if(l=="-")
      a[i].l=-1;
    else{
      a[i].l=stoi(l);
      have[stoi(l)]=1;
    }
    if(r=="-")
      a[i].r=-1;
    else{
      a[i].r=stoi(r);
      have[stoi(r)]=1;
    }
  }
  while(have[root]!=0)  root++;//得到根结点
  dfs(root,1);//注意第一个结点编号为1
  //dfs(root,0);
  if(maxn==n)
    cout<<"YES "<<ans;
  else
    cout<<"NO "<<root;
  system("pause");
    return 0;   
}