Complete Binary Tree (25)

时间限制 400 ms 内存限制 65536 kB 代码长度限制 16000 B 判题程序 Standard 作者 CHEN, Yue Given a tree, you are supposed to tell if it is a complete binary tree.

Input Specification:

Each input file contains one test case. For each case, the first line gives a positive integer N (<=20) which is the total number of nodes in the tree – and hence the nodes are numbered from 0 to N-1. Then N lines follow, each corresponds to a node, and gives the indices of the left and right children of the node. If the child does not exist, a “-” will be put at the position. Any pair of children are separated by a space.

Output Specification:

For each case, print in one line “YES” and the index of the last node if the tree is a complete binary tree, or “NO” and the index of the root if not. There must be exactly one space separating the word and the number.

Sample Input 1: 9 7 8 - - - - - - 0 1 2 3 4 5 - - - - Sample Output 1: YES 8 Sample Input 2: 8 - - 4 5 0 6 - - 2 3 - 7 - - - - Sample Output 2: NO 1

求指教！哪位大神帮看看这个段错误是怎么出的？郁闷中～～～～

#include<cstdio> #include<queue> #include<algorithm> using namespace std; const int maxn=1000; struct Node{ int l,r; int v; }node[maxn]; int n; int mk[maxn]; void LevelOrder(int root){ bool isComplete=true; bool flag=false; int cnt=0; queue<Node>q; q.push(node[root]); while(q.size()){ Node x=q.front(); q.pop(); cnt++; if(x.l==-1&&x.r!=-1){ isComplete=false; printf("NO %d",root); return; } if(flag==false){ if(x.l==-1||x.r==-1)flag=true; }else{//flag==true if(x.l!=-1||x.r!=-1){ isComplete=false; printf("NO %d",root); return; } } if(x.l!=-1)q.push(node[x.l]); if(x.r!=-1)q.push(node[x.r]); if(cnt==n&&isComplete==true){ printf("YES %d",x.v); return; } } } int main(){ scanf("%d",&n); fill(mk,mk+n,1); for(int i=0;i<n;i++){ getchar(); char a,b; int x,y; scanf("%c %c",&a,&b); if(a=='-'){ x=-1; }else{ x=a-'0'; mk[x]=0; } if(b=='-'){ y=-1; }else{ y=b-'0'; mk[y]=0; } //printf("x=%d y=%d\n",x,y); node[i].l=x; node[i].r=y; node[i].v=i; } int root=-1; for(int i=0;i<n;i++){ if(mk[i]==1){ root=i; break; } } //printf("root=%d\n",root); LevelOrder(root); return 0; }