本文主要是介绍AcWing 1600：完全二叉树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
【题目来源】
https://www.acwing.com/problem/content/1602/
【题目描述】
给定一个树，请你判断它是否是完全二叉树。
【输入格式】
第一行包含整数 N，表示树的结点个数。
树的结点编号为 0∼N−1。
接下来 N 行，每行对应一个结点，并给出该结点的左右子结点的编号，如果某个子结点不存在，则用 - 代替。
【输出格式】
如果是完全二叉树，则输出 YES 以及最后一个结点的编号。
如果不是，则输出 NO 以及根结点的编号。
【数据范围】
1≤N≤20
【输入样例1】
9
7 8
- -
- -
- -
0 1
2 3
4 5
- -
- -
【输出样例1】
YES 8
【输入样例2】
8
- -
4 5
0 6
- -
2 3
- 7
- -
- -
【输出样例2】
NO 1
【算法分析】
● 树的结点编号为 0∼N−1，而 1≤N≤20，所以结点编号是有二位数的，编码时要注意处理。
● 字符 ‘0’~‘9’ 转数字。例如，利用 ‘9’-‘0’ 得到数字 9。其他以此类推。
● 样例 1 及样例 2 对应的二叉树如下所示。显然，样例 1 是一个完全二叉树。
● 本例中，输入样例的行数，事实上就是结点的编号。
【算法代码】
#include <bits/stdc++.h>
using namespace std;const int N=25;
struct node {int le,ri;int id;
} tr[N];
bool st[N];int n;
int idx;
int maxv;void check(int u,int k) { //find last nodeif(u==-1) return;if(k>maxv) {maxv=k;idx=u;}check(tr[u].le,2*k);check(tr[u].ri,2*k+1);
}int main() {cin>>n;for(int i=0; i<n; i++) { //id from 0 to n-1string a,b;cin>>a>>b;if(a!="-") {int t=0;for(int i=0; i<a.size(); i++)t=t*10+(a[i]-'0'); //Convert string to numbertr[i].le=t;st[tr[i].le]=true;} else tr[i].le=-1;if(b!="-") {int t=0;for(int i=0; i<b.size(); i++)t=t*10+(b[i]-'0'); //Convert string to numbertr[i].ri=t;st[tr[i].ri]=true;} else tr[i].ri=-1;tr[i].id=i;}int root=-1;for(int i=0; i<n; i++) {if(!st[i]) {root=i;break;}}check(root,1);if(maxv==n) cout<<"YES "<<idx<<endl;else cout<<"NO "<<root<<endl;return 0;
}/*
in:
9
7 8
- -
- -
- -
0 1
2 3
4 5
- -
- -out:
YES 8---------in:
8
- -
4 5
0 6
- -
2 3
- 7
- -
- -out:
NO 1
*/
【参考文献】
https://www.acwing.com/solution/content/97561/
这篇关于AcWing 1600：完全二叉树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
