1110 Complete Binary Tree （25 分)

2019-04-24

1110 Complete Binary Tree （25 分)

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

作者: CHEN, Yue

单位: 浙江大学

时间限制: 400 ms

内存限制: 64 MB

代码长度限制: 16 KB

题目大意

给出一个棵树的结构，判断此数是否为完全二叉树。

分析

层序遍历。用一个变量记录遍历到的结点数，遍历到第一个空结点即退出。最后比较遍历过结点数的和应有结点数。注意这里结点编号可能是2位的。一开始没注意，测试点2，3，4一直错。

代码

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
#include <deque>
#include <queue>
#include <map>
#include <set>
#include <cstring>
#include <cmath>
#include <sstream>

using namespace std;
int n;
int showup[21];
vector<int> tree[21];

int main() {
    cin >> n;
    string lf,rt;
    int l, r;
    for (int i = 0; i < n; i++) {
        cin>>lf>>rt;
        l = isdigit(lf[0]) ? stoi(lf) : -1;
        r = isdigit(rt[0]) ? stoi(rt) : -1;
        tree[i].push_back(l);
        tree[i].push_back(r);
        if (l != -1)
            showup[l] = 1;
        if (r != -1)
            showup[r] = 1;
    }
    int head;
    for (int i = 0; i < n; i++)
        if (showup[i] == 0) {
            head = i;
            break;
        }
    int last;
    deque<int> q;
    q.push_back(head);
    int c = 0, cur;

    while (!q.empty()) {
        last=cur;
        cur = q.front();
        q.pop_front();
        if(cur==-1)
            break;
        l = tree[cur][0];
        r = tree[cur][1];
        q.push_back(l);
        q.push_back(r);
        c++;
    }
    if (c!=n)
        cout << "NO " << head << endl;
    else
        cout << "YES " << last<< endl;
    return 0;
}