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.

9
7 8
- -
- -
- -
0 1
2 3
4 5
- -
- -

YES 8

8
- -
4 5
0 6
- -
2 3
- 7
- -
- -

NO 1

解答

#include<iostream>
#include<vector>
#include<queue>
#include<string>

using namespace std;

int GetRoot(vector<pair<int, int>> v, int node)
{
int i;
for (i = 0; i < v.size(); i++) {
if (v[i].first == node || v[i].second == node)
return GetRoot(v, i);
}
if (i == v.size())  return node;
return i;
}

void Check(vector<pair<int, int>> v, int root) {
queue<int> nodes;
int p, last;
bool nullTag = false, complete = true;
nodes.push(root);
while (!nodes.empty()) {
p = nodes.front();
nodes.pop();
if (p == -1) nullTag = true;
else {
last = p;
if (nullTag == true)
complete = false;
nodes.push(v[p].first);
nodes.push(v[p].second);
}
}
if (complete) printf("YES %d", last);
else printf("NO %d", root);
}

int main()
{
int n;
string a, b;
int f, s;
vector<pair<int, int>> v;
cin >> n;
if (n == 0) {
printf("YES 0");
return 0;
}
for (int i = 0; i < n; i++) {
cin >> a >> b;
if (a == "-") f = -1;
else f = stoi(a);
if (b == "-") s = -1;
else s = stoi(b);
v.push_back(pair<int, int>(f, s));
}
int root = 0;
for (int i = 0; i < v.size(); i++) {
if (v[i].first != -1) {
root = GetRoot(v, v[i].first);
break;
}
if (v[i].second != -1) {
root = GetRoot(v, v[i].second);
break;
}
}
Check(v, root);
return 0;
}