Source:
Description:
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 (≤) 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, orNO
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
Keys:
- 完全二叉树(Complete Binary Tree)
Attention:
- atoi(s.c_str()); 字符串转化为int,atof 对应 double,atoll 对应 long long;
- 含非数字则截取前面的数字部分,首字符非数字则返回0
Code:
1 #include<cstdio> 2 #include<string> 3 #include<queue> 4 #include<iostream> 5 using namespace std; 6 const int M=25; 7 int h[M]={0}; 8 struct node 9 { 10 int left,right; 11 }tree[M]; 12 13 bool isComplete(int root, int &last) 14 { 15 queue<int> q; 16 q.push(root); 17 while(!q.empty()) 18 { 19 root = q.front(); 20 q.pop(); 21 if(root != -1) 22 { 23 last = root; 24 q.push(tree[root].left); 25 q.push(tree[root].right); 26 } 27 else 28 { 29 while(!q.empty()) 30 { 31 if(q.front() != -1) 32 return false; 33 q.pop(); 34 } 35 } 36 } 37 return true; 38 } 39 40 int main() 41 { 42 #ifdef ONLINE_JUDGE 43 #else 44 freopen("Test.txt", "r", stdin); 45 #endif 46 47 int n,root,last; 48 scanf("%d", &n); 49 for(int i=0; i<n; i++) 50 { 51 string l,r; 52 cin >> l >> r; 53 if(l == "-") 54 tree[i].left=-1; 55 else{ 56 tree[i].left = atoi(l.c_str()); 57 h[tree[i].left]=1; 58 } 59 if(r == "-") 60 tree[i].right=-1; 61 else{ 62 tree[i].right = atoi(r.c_str()); 63 h[tree[i].right]=1; 64 } 65 } 66 for(int i=0; i<n; i++){ 67 if(h[i]==0){ 68 root=i; 69 break; 70 } 71 } 72 if(isComplete(root, last)) 73 printf("YES %d", last); 74 else 75 printf("NO %d", root); 76 77 return 0; 78 }