[PAT] A1110 Complete Binary Tree

完全二叉树

题目大意

给出各个结点的左右孩子，问这棵树是不是完全二叉树，若是则输出YES和最后一个结点编号；若不是则输出NO和根节点编号。N个结点编号0~N-1。

思路

结构体数组保存树，为了找到根节点，输入时用bool数组ifchild记录，若有孩子，则该孩子的ifchild值为true，最后不是ture的就是根节点。根据父子关系遍历一遍该树，求出最大下标的和n比较。求最大下标的时候顺便保存其对应的结点编号。（一开始自己写的复杂代码是：保存每个下标，并将该下标再建立一个bool型数组标记是否填入下标值，若最后没有标记则是非完全二叉树。但这样非常多余，不必保存每个下标。）

改进

(1) string转到整数有stoi(str)函数，无需手写,但要保证string里面都是数字！！！ (2) 完全二叉树一定把前面的下标充满，即：最大的下标值 == 最大的节点数；不完全二叉树前满一定有位置是空，会往后挤：最大的下标值 > 最大的节点数。根据这个可以直接在递归中求出最大下标，无需保存。

tips

一定要注意输入有数字和符号的情况，统一用string输入然后stoi。有可能数字不止一位数！！！

AC代码

#define _CRT_SECURE_NO_WARNINGS #include<iostream> #include<cstdio> #include<string> using namespace std; #define N 200 struct Node { int lchild, rchild; }node[N]; bool ifchild[N] = { false }; int maxvalue = 0, maxid; void pre(int root, int index) { if (maxvalue < index) { maxvalue = index; maxid = root; } if (node[root].lchild != -1)pre(node[root].lchild, index * 2); if (node[root].rchild != -1)pre(node[root].rchild, index * 2 + 1); } int main() { int i, n; scanf("%d", &n); for (i = 0;i < n;i++) { string s_tleft, s_tright; cin >> s_tleft >> s_tright; if (s_tleft == "-")node[i].lchild = -1; else { node[i].lchild = stoi(s_tleft); ifchild[node[i].lchild] = true; } if (s_tright == "-")node[i].rchild = -1; else { node[i].rchild = stoi(s_tright); ifchild[node[i].rchild] = true; } } int root = 0; for (i = 0;i < n;i++) if (ifchild[i] == false) { root = i; break; } if (n != 0)pre(root, 1); if (maxvalue != n) printf("NO %d", root); else printf("YES %d", maxid); return 0; }

初次代码：

#define _CRT_SECURE_NO_WARNINGS #include<iostream> #include<cstdio> #include<string> using namespace std; #define N 200 struct Node { int lchild, rchild, index; }node[N]; bool ifchild[N] = { false }, ifindex[N + 1] = { false }; int maxvalue = 0, maxid; int strtoint(string a) { if (a == "-")return -1; else { int ans = 0; for (int i = 0;i < a.size();i++) { ans = ans * 10 + a[i] - '0'; } return ans; } } void pre(int root, int index) { node[root].index = index; ifindex[index] = true; if (maxvalue < index) { maxvalue = index; maxid = root; } if (node[root].lchild != -1)pre(node[root].lchild, index * 2); if (node[root].rchild != -1)pre(node[root].rchild, index * 2 + 1); } int main() { int i, n; scanf("%d", &n); for (i = 0;i < n;i++) { string s_tleft, s_tright; cin >> s_tleft >> s_tright; int tleft = strtoint(s_tleft), tright = strtoint(s_tright); if (tleft >= 0 && tleft < N) { node[i].lchild = tleft; ifchild[tleft] = true; } else node[i].lchild = -1; if (tright >= 0 && tright < N) { node[i].rchild = tright; ifchild[tright] = true; } else node[i].rchild = -1; } int root = 0; for (i = 0;i < n;i++) if (ifchild[i] == false) { root = i; break; } if (n != 0)pre(root, 1); i = 1; while (ifindex[i] && i <= n)i++; if (i != n + 1) printf("NO %d", root); else printf("YES %d", maxid); return 0; }