【LSP】c_pat_完全二叉树判定（利用性质）
http://cdn.u1.huluxia.com/g4/M01/5B/44/rBAAdl9u_zCANG7dAACt4WdlvYs137.jpg
第一行包含整数 N，表示树的结点个数。
树的结点编号为 0～N?1。
接下来 N 行，每行对应一个结点，并给出该结点的左右子结点的编号，如果某个子结点不存在，则用 - 代替。
输出格式
如果是完全二叉树，则输出 YES 以及最后一个结点的编号。
如果不是，则输出 NO 以及根结点的编号。http://cdn.u1.huluxia.com/g4/M01/5B/44/rBAAdl9u_zCACY1SAACdPFl39Uo223.png
思路
这里千万不要被题目给定的结点标号弄混淆（给的仅仅是一个编号而已)，这里考的是完全二叉树的性质：如果这棵树是完全二叉树，则从上至下，再从左到右一定不会有空隙；
#include<bits/stdc++.h>
using namespace std;
const int N=25;
struct node {
int l=-1,r=-1;
} A;
int maxk, last_node, has_fa;
void dfs(int root, int k) {
if (k>maxk) {
last_node=root;
maxk=k;
}
if (A.l!=-1) dfs(A.l, 2*k);
if (A.r!=-1) dfs(A.r, 2*k+1);
}
int main() {
std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int n; cin>>n;
for (int i=0; i<n; i++) {
string l,r; cin>>l>>r;
if (l!="-") A.l=stoi(l), has_fa=1;
if (r!="-") A.r=stoi(r), has_fa=1;
}
int root=0;
while (has_fa) root++;
dfs(root, 1);
if (maxk>n) cout<<"NO"<<' '<<root;
else cout<<"YES"<<' '<<last_node;
return 0;
}http://cdn.u1.huluxia.com/g4/M01/5B/44/rBAAdl9u_zGAMZ9vAADNVZavRf0304.jpg
页:
[1]