个人练习-PAT甲级-1110 Complete Binary Tree

本文主要是介绍个人练习-PAT甲级-1110 Complete Binary Tree，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接https://pintia.cn/problem-sets/994805342720868352/problems/994805359372255232

题目大意：给出一棵树的结构，判断是否为完全二叉树。如果是，输出YES和最后一个节点的index；否则输出NO和根节点index

思路：建树，找到根节点。然后遍历树，给每个节点赋值一个val，从1开始，那么二叉树，左儿子val = val*2，右儿子val = val*2 + 1。因为节点数N已知，所以合法（是完全二叉树）时这个val <= N，在val == N的时候得到最后一个节点；否则不是完全二叉树，直接return停止遍历，出来输出结果就行。

void inOrder(int idx, int val) {if (ret == true) {if (tree[idx].left != -1)inOrder(tree[idx].left, val * 2);tree[idx].val = val;if (val > N){ret = false;return;}else if (val == N)last_idx = idx;if (tree[idx].right != -1)inOrder(tree[idx].right, val * 2 + 1);}
}

完整代码

#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
#include <queue>
#include <map>
#include <set>using namespace std;class Node{
public:int val;int left, right;
};int N, last_idx;
vector<Node> tree;
vector<bool> isRoot;
bool ret;void inOrder(int idx, int val) {if (ret == true) {if (tree[idx].left != -1)inOrder(tree[idx].left, val * 2);tree[idx].val = val;if (val > N){ret = false;return;}else if (val == N)last_idx = idx;if (tree[idx].right != -1)inOrder(tree[idx].right, val * 2 + 1);}
}int main() {scanf("%d\n", &N);tree.resize(N);isRoot.resize(N, true);ret = true;for (int i = 0; i < N; i++) {string str1, str2;cin >> str1 >> str2;if (str1[0] != '-') {tree[i].left = stoi(str1);isRoot[stoi(str1)] = false;}elsetree[i].left = -1;if (str2[0] != '-') {tree[i].right = stoi(str2);isRoot[stoi(str2)] = false;}elsetree[i].right = -1;}int root = -1;for (int i = 0; i < N; i++) {if (isRoot[i] == true) {root = i;break;}}inOrder(root, 1);if (ret == true)printf("YES %d", last_idx);elseprintf("NO %d", root);return 0;
}