题目大意：

给出一棵二叉树，判断其是不是完全二叉树，若是，输出“YES”，并输出最后一个结点的编号，若不是，输出“NO”，并输出根结点的编号。

思路：

这道题既可以用BFS,也可以用DFS。

BFS代码如下：

#include<iostream>
#include<algorithm>
#include<math.h>
#include<vector>
#include<queue>
using namespace std;

int n;
struct tree{
    int id;
    int left,right;
};

vector<tree> t;
bool flag[25]={false};
int last_id;//最后一个结点的id

bool judge(int root){
    bool tag=false;
    queue<tree> q;
    q.push(t[root]);
    while(!q.empty()){
        tree temp=q.front();
        q.pop();
        if(temp.left==-1&&temp.right!=-1){//若一个结点有右孩子但没有左孩子
            return false;
        }
        if(tag){//若tag==true，则进来的结点必须是叶子结点
            if(temp.left!=-1||temp.right!=-1){
                return false;
            }
        }

        if(temp.right==-1){//若一个结点没有右孩子，剩下进入队列的结点必须是叶子结点
			tag=true;//标记tag=true
        }
		if(temp.left!=-1){
			q.push(t[temp.left]);
		}
		if(temp.right!=-1){
			q.push(t[temp.right]);
		}
		if(q.empty()){
            last_id=temp.id;
		}
    }
    return true;
}

int main(){
    cin>>n;
    t.resize(n);

    string l_s,r_s;
    for(int i=0;i<n;i++){
        t[i].id=i;
        cin>>l_s>>r_s;
        if(l_s[0]!='-'){
            int num=0;
            for(int j=0;j<l_s.length();j++){
                num=num*10+l_s[j]-'0';
            }
            t[i].left=num;
            flag[num]=true;
        }else{
            t[i].left=-1;
        }

        if(r_s[0]!='-'){
            int num=0;
            for(int j=0;j<r_s.length();j++){
                num=num*10+r_s[j]-'0';
            }
            t[i].right=num;
            flag[num]=true;
        }else{
            t[i].right=-1;
        }
    }

    int root;
    for(int i=0;i<n;i++){
        if(flag[i]==false){
            root=i;
            break;
        }
    }

    if(!judge(root)){
        cout<<"NO "<<root;
    }else{
        cout<<"YES "<<last_id;
    }

    return 0;
}

DFS代码如下：

我们把树的每一个结点进行编号，若dfs完成后树的最大结点编号不等于n，则说明不是完全二叉树。

//dfs
#include<iostream>
#include<algorithm>
#include<math.h>
#include<vector>
#include<queue>
using namespace std;

int n;
struct tree{
    int id;
    int left,right;
};

vector<tree> t;
bool flag[25]={false};
int last_id;//最后一个结点的id
int max_index=-1;

void dfs(int root,int index){
    if(index>max_index){
        max_index=index;
        last_id=root;
    }

    if(t[root].left==-1&&t[root].right==-1){
        return;
    }

    if(t[root].left!=-1){
        dfs(t[root].left,2*index);
    }
    if(t[root].right!=-1){
        dfs(t[root].right,2*index+1);
    }
}

int main(){
    cin>>n;
    t.resize(n);

    string l_s,r_s;
    for(int i=0;i<n;i++){
        t[i].id=i;
        cin>>l_s>>r_s;
        if(l_s[0]!='-'){
            int num=0;
            for(int j=0;j<l_s.length();j++){
                num=num*10+l_s[j]-'0';
            }
            t[i].left=num;
            flag[num]=true;
        }else{
            t[i].left=-1;
        }

        if(r_s[0]!='-'){
            int num=0;
            for(int j=0;j<r_s.length();j++){
                num=num*10+r_s[j]-'0';
            }
            t[i].right=num;
            flag[num]=true;
        }else{
            t[i].right=-1;
        }
    }

    int root;
    for(int i=0;i<n;i++){
        if(flag[i]==false){
            root=i;
            break;
        }
    }

    dfs(root,1);
    if(max_index!=n){
        cout<<"NO "<<root;
    }else{
        cout<<"YES "<<last_id;
    }

    return 0;
}