完全二叉树
题目描述
给定一棵树，你应该指出它是否是一个完全二叉树。 对于每种情况，第一行给出正整数N（≤20），它是树中节点的总数（节点从0到N-1编号）。 然后是N行，第i行对应一个节点i，并给出节点i左右子节点的索引。 如果孩子不存在，则 - 将被置于该位置。 对于每种情况，如果树是完全二叉树，则在一行中打印YES和层序遍历的最后一个节点的索引，或者如果不是，则打印NO和根的索引。 必须有一个空格分隔单词和数字。
 

#include <bits/stdc++.h>
#include<cstring>
#include<queue>
using namespace std;

const int N = 30;
int n;
int l[N], r[N];
bool hf[N];
int final;
bool judge(int root)
{
    queue<int>qu;
    qu.push(root);
    while(!qu.empty())
    {
    	if(!(l[qu.front()]!=-1&&r[qu.front()]!=-1)) break;
    	int x=qu.front();
    	qu.pop();
    	qu.push(l[x]);
    	qu.push(r[x]);
	}
	qu.pop();
	while(!qu.empty())
	{
		int x=qu.front();
		if(!(l[x]==-1&&r[x]==-1))
		{
			return false;
		}
		qu.pop();
		if(qu.size()==1)
		{
			final=qu.front();
		}
	}
	return true;
}

int main()
{
    cin >> n;
    for(int i = 0; i < n; i++)
    {
        char a, b;
        cin >> a >> b;
        if(a !='_')
        {
            l[i] = a-'0';
            hf[a-'0'] = true;
        }
        else l[i] = -1;
        if(b != '_')
        {
            r[i] = b-'0';
            hf[b-'0'] = true;
        }
        else r[i] = -1;
    }
    int root = 0;
    while(hf[root]) root ++;
    if(judge(root))
    {
    	cout<<"YES "<<final;
	}
	else
	{
		cout<<"NO "<<root;
	}
}