题意：判断一个节点为n的二叉树是否为完全二叉树。Yes输出完全二叉树的最后一个节点，No输出根节点。
建树，然后分别将该树与节点树为n的二叉树相比较，统计对应的节点个数，如果为n，则为完全二叉树，否则即不是。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string.h> using namespace std;
const int maxn=;
int two[];
int lastNode;
struct Node{
int left,right;
int id;
}tree[maxn],cbt[maxn]; /*
将输入给的二叉树和节点为n的完全二叉树一个个作比较，计算对应的节点个数
如果节点个数为n，则二叉树为完全二叉树。
i为完全二叉树的当前节点编号。
root为输入二叉树的对应节点。
*/
int compare(int root,int i,int n){
int res1=-,res2=-;
if(root==-){
return ;
}
if(i==n)
lastNode=root; //记录完全二叉树的最后一个节点的id
int sum=; if(*i<=n){
sum+=compare(tree[root].left,i*,n);
}
if(*i+<=n){
sum+=compare(tree[root].right,i*+,n);
}
bool flag1=false,flag2=false;
if((*i<=n&&tree[root].left!=-)||(*i>n&&tree[root].left==-))
flag1=true;
if((*i+<=n&&tree[root].right!=-)||(*i+>n&&tree[root].right==-))
flag2=true;
if(flag1 && flag2)
sum++;
return sum;
}
int main()
{
int n;
scanf("%d",&n);
char str1[],str2[];
int a;
int vis[maxn];
memset(vis,-,sizeof(vis));
for(int i=;i<n;i++){
scanf("%s %s",str1,str2);
tree[i].id=i;
if(str1[]=='-')
tree[i].left=-;
else{
a=atoi(str1);
tree[i].left=a;
vis[a]=;
}
if(str2[]=='-')
tree[i].right=-;
else{
a=atoi(str2);
tree[i].right=a;
vis[a]=;
}
}
int root;
for(int i=;i<n;i++){
if(vis[i]==-)
root=i;
} if(compare(root,,n)==n){
printf("YES %d",lastNode);
}
else{
printf("NO %d",root);
}
return ;
}
该博客里的解题方法要比我好一点，即按照层次遍历该二叉树，每遍历一个节点cnt++，直到为-1。此时cnt=n，则Yes，否则No。