pat-a1110. Complete Binary Tree (25)

这个题西先是没好好读题，没注意到no后面要输出根节点。。

然后是写太快了没注意范围，以为节点编号都是个位数。这个点错了我好多。。

#include<cstdio> #include<map> #include<vector> #include<queue> #include<cstring> using namespace std; map<int,vector<int> >tree; int p[50]; int last; bool bfs(int root){ queue<int> q; int flag=1; q.push(root); while(!q.empty()){ int t=q.front(); q.pop(); if(flag==1&&t==-1){ flag=0; } if(flag==0&&t!=-1) return 0; if(t!=-1){ last=t; q.push(tree[t][0]); q.push(tree[t][1]); } } return 1; } int fun(char* s){ int ans=0; int len=strlen(s); for(int i=0;i<len;++i) ans=ans*10+s[i]-'0'; return ans; } int main(){ int n; scanf("%d",&n); char a[2],b[2]; for(int i=0;i<n;++i){ scanf("%s%s",a,b); int x=0; if(a[0]!='-') x=fun(a); else x=-1; if(x!=-1) p[x]=1; tree[i].push_back(x); if(b[0]!='-') x=fun(b); else x=-1; tree[i].push_back(x); if(x!=-1) p[x]=1; } int root=-1; for(int i=0;i<n;++i){ if(p[i]==0){ root=i; break; } } if(bfs(root)) printf("YES %d\n",last); else printf("NO %d\n",root); return 0; }

时间限制 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