1110 完全二叉树

给定一个树，请你判断它是否是完全二叉树。

输入格式

第一行包含整数 N，表示树的结点个数。

树的结点编号为 0∼N−1。

接下来 N 行，每行对应一个结点，并给出该结点的左右子结点的编号，如果某个子结点不存在，则用 - 代替。

输出格式

如果是完全二叉树，则输出 YES 以及最后一个结点的编号。

如果不是，则输出 NO 以及根结点的编号。

数据范围

1≤N≤20

输入样例1：

9
7 8
- -
- -
- -
0 1
2 3
4 5
- -
- -

输出样例1：

YES 8

输入样例2：

8
- -
4 5
0 6
- -
2 3
- 7
- -
- -

输出样例2：

NO 1

实现代码：

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=25;
int l[N],r[N],vis[N],max_n,lastx;
void dfs(int x,int k){
    if(k>max_n){
        max_n=k;
        lastx=x;
    }
    if(l[x]!=-1)dfs(l[x],k*2);
    if(r[x]!=-1)dfs(r[x],k*2+1);
}
int main(){
    int n;
    cin>>n;
    memset(l,-1,sizeof l);
    memset(r,-1,sizeof r);
    for(int i=0;i<n;i++){
        string a,b;
        cin>>a>>b;
        if(a!="-")l[i]=stoi(a),vis[l[i]]=1;
        if(b!="-")r[i]=stoi(b),vis[r[i]]=1;
    }
    int root=0;
    for(int i=0;i<n;i++){
        if(!vis[i]){
            root=i;
            break;
        }
    }
    dfs(root,1);
    if(max_n>n)cout<<"NO "<<root<<endl;
    else cout<<"YES "<<lastx<<endl;
    return 0;
}