1110 Complete Binary Tree（附测试点2，3，4，6分析）

题目：

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;
}