题目：
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
题目大意：
给出一个n表示有n个结点，这n个结点为0~n-1，给出这n个结点的左右孩子，求问这棵树是不是完全二叉树
思路：
测试点2，3，4:
因为结点可能是两位数，我之前用char类型去获取左右孩子结点，但是结点可能是两位数，所以需要用string
测试点6：
当结点个数为1时，一定是完全二叉树
如何判断是完全二叉树？
除了最底层之外，每一层的结点个数为2^n
最底层的结点一定是从左至右“填充”
易错点：
scanf("%c")输入字符时，需要注意： %c前没空格，scanf()将读取标准输入流中的第一个字符，%c前有空格，scanf()则读取标准输入流中第一个非空白字符，屏蔽了空白字符
代码：（满分）
#include<stdio.h> #include<iostream> #include<algorithm> #include<string.h> #include<queue> #include<vector> #include<math.h> using namespace std; int n, root, treeDeep = -1; bool isRoot[25]; vector<int> deep[25]; struct Node{ int d, lchild, rchild; }nodes[25]; void bfs(int root){ queue<int> q; q.push(root); while(!q.empty()){ int tmp = q.front(); q.pop(); deep[nodes[tmp].d].push_back(tmp); if(nodes[tmp].d > treeDeep) treeDeep = nodes[tmp].d; int l = nodes[tmp].lchild; int r = nodes[tmp].rchild; if(l != -1){ nodes[l].d = nodes[tmp].d + 1; q.push(l); } if(r != -1){ nodes[r].d = nodes[tmp].d + 1; q.push(r); } } } int main(){ scanf("%d", &n); fill(isRoot, isRoot + n, 1); for(int i = 0; i < n; i++){ string l, r; cin>>l>>r; // cout<<l<<" "<<r<<endl; if(l != "-"){ nodes[i].lchild = atoi(l.c_str()); isRoot[atoi(l.c_str())] = 0; }else{ nodes[i].lchild = -1; } if(r != "-"){ nodes[i].rchild = atoi(r.c_str()); isRoot[atoi(r.c_str())] = 0; }else{ nodes[i].rchild = -1; } } for(int i = 0; i < n; i++){ if(isRoot[i]){ root = i; break; } } nodes[root].d = 0; bfs(root); bool flag = true; for(int i = 0; i < treeDeep; i++){ if(pow(2, i) != deep[i].size()){ flag = false; } } int num = 0, lastNode = 0; if(treeDeep == 0){ printf("YES %d", lastNode); return 0; } for(int i = 0; i < deep[treeDeep - 1].size(); i++){ int node = deep[treeDeep - 1][i]; if(nodes[node].lchild == -1 && nodes[node].rchild != -1){ flag = false; break; } if(nodes[node].lchild == -1 && nodes[node].rchild == -1){ if((pow(2, treeDeep) - 1) + num != n){ flag = false; } break; } if(nodes[node].lchild != -1 && nodes[node].rchild == -1){ num++; if((pow(2, treeDeep) - 1) + num != n){ flag = false; } lastNode = nodes[node].lchild; break; } if(nodes[node].lchild != -1){ num++; } if(nodes[node].rchild != -1){ num++; lastNode = nodes[node].rchild; } } if(!flag){ printf("NO %d", root); }else{ printf("YES %d", lastNode); } return 0; }
优化思路：递归出最大的下标值，完全二叉树一定把前面的下标充满： 最大的下标值 == 最大的节点数；不完全二叉树前满一定有位置是空，会往后挤： 最大的下标值 > 最大的节点数
优化代码：（更简单）
#include <iostream> using namespace std; struct node{ int l, r; }a[100]; int maxn = -1, ans; void dfs(int root, int index) { if(index > maxn) { maxn = index; ans = root; } if(a[root].l != -1) dfs(a[root].l, index * 2); if(a[root].r != -1) dfs(a[root].r, index * 2 + 1); } int main() { int n, root = 0, have[100] = {0}; cin >> n; for (int i = 0; i < n; i++) { string l, r; cin >> l >> r; if (l == "-") { a[i].l = -1; } else { a[i].l = stoi(l); have[stoi(l)] = 1; } if (r == "-") { a[i].r = -1; } else { a[i].r = stoi(r); have[stoi(r)] = 1; } } while (have[root] != 0) root++; dfs(root, 1); if (maxn == n) cout << "YES " << ans; else cout << "NO " << root; return 0; }