PAT甲级 1110 Complete Binary Tree

题目链接

PAT甲级 1110 Complete Binary Tree

思路

第一次的写法不是很好。
对于这种完全二叉树的层序遍历，比较烦人的就是空孩子使得处理很麻烦。
思来想去还是把空位置也入队比较好。

这样的话，访问到空指针的时机被推迟了一个level
而完全二叉树的叶子之间的层间距不会超过1
所以对于合法的完全二叉树，我们访问到空孩子的时机不会早于访问树中的任何叶节点

这样的话，当访问到空指针的时候：

1. 对于合法的完全二叉树，一定树中所有元素都遍历完了，故有n == 0
2. 若此时仍有n > 0，否则就说明层间有空隙，故不合法。

所以只要在访问到空指针的时候加入我们的判断即可，并记录还未访问的树节点个数。

代码

#include<bits/stdc++.h>using namespace std;vector<int> parent;
vector<pair<int, int>> children;int last = -1;int main() {int n;cin >> n;children.resize(n + 1, {-1, -1});parent.resize(n + 1, -1);for(int i = 0; i < n; ++i) {string left, right;cin >> left >> right;if(left != "-") {children[i].first = stoi(left);parent[stoi(left)] = i;}if(right != "-") {children[i].second = stoi(right);parent[stoi(right)] = i;}}int root = -1;for(int i = 0; i < n; ++i) {if(parent[i] == -1) {root = i;break;}}assert(root != -1);queue<int> q;q.push(root);bool flag = true;while(! q.empty() && flag) {int size = q.size();int pre_is_null = 0;while(size--) {auto node = q.front();q.pop();if(node == -1) {if(n > 0) {flag = false;}break;}last = node;--n;auto left = children[node].first;auto right = children[node].second;q.push(left);q.push(right);}}if(! flag) {cout << "NO " << root;} elsecout << "YES " << last;cout << endl;
}