[数据结构与算法]A1110 Complete Binary Tree (25 分)

?思路：由完全二叉树的性质即叶子节点只可能在最后两层，相对于同高度的满二叉树的差别在于最后一行右边是空的，左边是连续的叶子节点，因此可以想到用BFS遍历，节点为空也加入遍历过程，当遍历到第n个节点时，如之前出现空节点，则不是完全二叉树（过程中记录最后一个节点last）。

注意跟A1102区别, N?(≤20) ，节点编号可能是两位！

#include <cstdio>
#include <cstring>
#include <string>
#include <queue>
#include <algorithm>
#include <iostream>
using namespace std;
const int maxn=30;
struct node{
    int l,r;
}Node[maxn];

bool BFS(int root,int &last,int n){
    queue<int>q;
    q.push(root);
    while(n>0){
        int now=q.front();
        q.pop();
        n--;
        if(now==-1) return false;
        last=now;
        q.push(Node[now].l);
        q.push(Node[now].r);
    }
    return true;
}

int main(){
    int n;
    bool notroot[maxn]={false};
    string left,right;
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        cin>>left>>right;
        if(left!="-"){
            if(left.size()==1) Node[i].l=left[0]-'0';
            if(left.size()>1) Node[i].l=10*(left[0]-'0')+left[1]-'0';
            notroot[Node[i].l]=true;
        }
        else Node[i].l=-1;
        if(right!="-"){
            if(right.size()==1) Node[i].r=right[0]-'0';
            if(right.size()>1) Node[i].r=10*(right[0]-'0')+right[1]-'0';
            notroot[Node[i].r]=true;
        }
        else Node[i].r=-1;
    }
    int ans;
    for(int i=0;i<n;i++){
        if(notroot[i]==false){
            ans=i;
            break;
        }
    }
    int last;
    if(BFS(ans,last,n)) printf("YES %d",last);
    else printf("NO %d",ans);
    return 0;
}