【LSP】c_pat_完全二叉树判定（利用性质）

无名

第一行包含整数 N，表示树的结点个数。
树的结点编号为 0～N?1。
接下来 N 行，每行对应一个结点，并给出该结点的左右子结点的编号，如果某个子结点不存在，则用 - 代替。
输出格式
如果是完全二叉树，则输出 YES 以及最后一个结点的编号。
如果不是，则输出 NO 以及根结点的编号。
思路
这里千万不要被题目给定的结点标号弄混淆（给的仅仅是一个编号而已)，这里考的是完全二叉树的性质：如果这棵树是完全二叉树，则从上至下，再从左到右一定不会有空隙；

#include<bits/stdc++.h>
using namespace std;
const int N=25;
struct node {
    int l=-1,r=-1;
} A[N];
int maxk, last_node, has_fa[N];

void dfs(int root, int k) {
    if (k>maxk) {
        last_node=root;
        maxk=k;
    }
    if (A[root].l!=-1) dfs(A[root].l, 2*k);
    if (A[root].r!=-1) dfs(A[root].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[stoi(l)]=1;
        if (r!="-") A.r=stoi(r), has_fa[stoi(r)]=1;
    }
    int root=0;
    while (has_fa[root]) root++;
    dfs(root, 1);
    if (maxk>n) cout<<"NO"<<' '<<root;
    else        cout<<"YES"<<' '<<last_node;
    return 0;
}