PAT A1110 Complete Binary Tree （25 分）——完全二叉树，字符串转数字-白红宇

PAT A1110 Complete Binary Tree （25 分）——完全二叉树，字符串转数字

阅读量：5164 次

发布时间：2019-06-13

本文共 2271 字，大约阅读时间需要 7 分钟。

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

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:

97 8- -- -- -0 12 34 5- -- -

Sample Output 1:

YES 8

Sample Input 2:

8- -4 50 6- -2 3- 7- -- -

Sample Output 2:

NO 1

1 #include 
       
         2 #include 
        
          3 #include 
         
           4 #include 
          
            5 #include 
           
             6 #include 
            
              7 #include 
             
               8 #include 
              
                9 #include 
               
                10 using namespace std;11 const int maxn = 30;12 int n,k;13 struct node{14 int l=-1,r=-1;15 }tree[maxn];16 int vis[maxn]={ 0};17 int main(){18 scanf("%d",&n);19 getchar();20 for(int i=0;i
                
                 >c1>>c2;23 getchar();24 int n1=-1,n2=-1;25 if(c1!="-"){26 n1=stoi(c1);27 vis[n1]=1;28 }29 if(c2!="-"){30 n2=stoi(c2);31 vis[n2]=1;32 }33 tree[i].l=n1;34 tree[i].r=n2;35 }36 int root=-1;37 for(int i=0;i

q;45 q.push(root);46 while(!q.empty()){47 now=q.front();48 q.pop();49 //printf("%d ",now);50 if(tree[now].l!=-1){51 if(flag==0)q.push(tree[now].l);52 else {53 flag2=1;54 break;55 }56 }57 else{58 flag=1;59 }60 if(tree[now].r!=-1){61 if(flag==0)q.push(tree[now].r);62 else {63 flag2=1;64 break;65 }66 }67 else{68 flag=1;69 }70 /*if(now!=-1){71 flag++;72 flag2=now;73 }74 else{75 if(flag==n){76 printf("YES %d",flag2);77 }78 else{79 printf("NO %d",root);80 }81 return 0;82 }83 q.push(tree[now].l);84 q.push(tree[now].r);85 */86 }87 if(flag2==1)printf("NO %d",root);88 else printf("YES %d",now);89 }

View Code

注意点：完全二叉树的判断就是看已经有节点没孩子了，后面节点却还有孩子，这树就不是完全二叉树。有三个点一直错误，一开始段错误，后来在结构体初始化了-1后答案错误，总找不到原因。后来才发现原来是读输入的时候错了，两位数就读不到了，不能用%c，要用string

转载于:https://www.cnblogs.com/tccbj/p/10453426.html

你可能感兴趣的文章