PAT（甲级）1110 Complete Binary Tree (25point(s)) 判断是不是完全二叉树

题目

题目链接

思路

题目大意：给一颗二叉树，判断是不是完全二叉树； 可以根据完全二叉树的性质来判断，在线性存储结构下，左孩子下标 = 2 * 父节点下标， 右孩子下标 = 2 * 父节点下标+ 1； 我们在输入节点过程中，如果一个节点是别人的孩子节点，那么他一定不是根节点，这样在输入完成后，在遍历一遍所有节点，就可以找到根节点； 然后从这个根节点出发开始DFS，输入两个参数，一个是这个节点的id，另一个是这个节点如果在线性表中应有的下标，如果下标大于全局最大值，那么更新最大值，并且记录这个节点的id，作为最后一个节点; 最后根据最大的下标是否等于节点个数判断是不是完全二叉树；

代码

#include <iostream> #include <vector> #include <algorithm> #include <set> using namespace std; const int maxn = 30; struct node{ int left, right; node(){ this->left = -1, this->right = -1; } }tree[maxn]; bool isRoot[maxn];//存储是不是根节点，如果读入过程中发现是叶节点，则标记为不是根节点 int last = -1, ans;//ans 记录最后一个节点,last记录最后一个节点在线性表的下标 //遍历每个节点，idx是当前这个节点的在线性表的下标，找到下标最大的数 void DFS(int root, int idx){ if(idx > last){ last = idx; ans = root; } //递归时注意判断一下，在叶节点就结束，而不是叶节点的下一层 if(tree[root].left != -1) DFS(tree[root].left, 2 * idx); if(tree[root].right != -1) DFS(tree[root].right, 2 * idx + 1); } int main() { fill(isRoot, isRoot + maxn, true); int n; scanf("%d", &n); string l, r; for(int i = 0; i < n; i ++){ cin >> l >> r; if(l != "-"){ tree[i].left = stoi(l); isRoot[stoi(l)] = false;//标记不是根节点 } if(r != "-"){ tree[i].right = stoi(r); isRoot[stoi(r)] = false; } } int root = 0; while(isRoot[root] == false) root ++;//找到根节点 DFS(root, 1); if(last == n) printf("YES %d\n", ans); else printf("NO %d\n", root); system("pause"); return 0; }