题意：给定一个二叉树，判断是否为完全二叉树，是则打印最后一个点，否则打印根节点
思路：先用结构体数组构建二叉树，然后判断，对于判断是否为一颗完全二叉树，如果是一颗完全二叉树，最大节点的下标一定是等于节点个数的，否则最大节点下标一定大于节点个数，中间位置有空，把最大节点向后挤。
代码：
#include<iostream> #include<string> using namespace std; struct node { int l, r; }nodes[25]; int n = 0, root = 0,ans = 0,maxn = 0,have[25]; void dfs(int root,int index) { if (index > maxn) { maxn = index;//记录当前最大的下标 ans = root;//记录当前最大下标的根节点 } if (nodes[root].l != -1)dfs(nodes[root].l, 2 * index); if (nodes[root].r != -1)dfs(nodes[root].r, 2 * index+1); } int main() { string s1, s2; cin >> n; for (int i = 0; i < n; i++) { cin >> s1 >> s2; if (s1 != "-") { nodes[i].l = stoi(s1); have[stoi(s1)] = 1; } else { nodes[i].l = -1; } if (s2 != "-") { nodes[i].r = stoi(s2); have[stoi(s2)] = 1; } else { nodes[i].r = -1; } } while (root < n&&have[root] == 1)root++; dfs(root,1); if (maxn == n) { cout << "YES" << " " << ans<<endl; } else { cout << "NO" << " " << root << endl; } system("pause"); return 0; }
