AcWing 1600. 完全二叉树
原题链接
简单
作者:
王小强
,
2021-02-11 18:01:02
,
所有人可见
,
阅读 429
千锤百炼
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
const int N = 22;
int n, hasParent[N];
string l, r;
// Definition for a binary tree node.
struct TreeNode {
int val;
TreeNode *left, *right;
TreeNode(int _val) : val(_val), left(nullptr), right(nullptr) {};
~TreeNode() {};
};
TreeNode* buildTree(vector<pair<int, int>>& data, int rootIdx) {
if (rootIdx == -1) return nullptr;
auto root = new TreeNode(rootIdx);
root->left = buildTree(data, data[rootIdx].first);
root->right = buildTree(data, data[rootIdx].second);
return root;
}
pair<bool, int> isCompleteTree(TreeNode* root) {
int last_id = -1; // 最后一个节点的ID
queue<TreeNode*> q{{root}};
while (not q.empty()) {
auto cur = q.front(); q.pop();
if (!cur) break;
last_id = cur->val;
q.emplace(cur->left);
q.emplace(cur->right);
}
while (not q.empty()) {
auto cur = q.front(); q.pop();
if (cur) return { false, -1 };
}
return { true, last_id };
}
int findRootId() {
int root_id = -1;
for (int i = 0; i < n; ++i) {
if (!hasParent[i]) {
root_id = i;
break;
}
}
return root_id;
}
int main(void) {
scanf("%d", &n);
vector<pair<int, int>> data(n);
for (int i = 0; i < n; ++i) {
cin >> l >> r;
if (isdigit(l[0])) hasParent[stoi(l)] = 1;
data[i].first = isdigit(l[0]) ? stoi(l) : -1;
if (isdigit(r[0])) hasParent[stoi(r)] = 1;
data[i].second = isdigit(r[0]) ? stoi(r) : -1;
}
int root_id = findRootId();
auto root = buildTree(data, root_id);
auto [ok, last_id] = isCompleteTree(root);
cout << (ok ? "YES " + to_string(last_id) : "NO " + to_string(root_id)) << endl;
return 0;
}