PAT甲级 1110 完全二叉树

原题链接

 给定一个树，请你判断它是否是完全二叉树。

输入格式
第一行包含整数 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

我的解法：

#include 
using namespace std;
const int N = 25;
int l[N], r[N];
bool has_father[N];
int maxk, maxid;
void dfs(int u, int k){
    if(u == -1) return;
    if(k > maxk){
        maxk = k;
        maxid = u;
    }
    
    dfs(l[u], 2 * k);
    dfs(r[u], 2 * k + 1);
}
int main(){
    memset(l, -1, sizeof l);
    memset(r, -1, sizeof r);
    int n;
    cin >> n;
    for(int i = 0; i < n; i ++ ){
        string lk, rk;
        cin >> lk >> rk;
        if(lk != "-") l[i] = stoi(lk), has_father[stoi(lk)] = true;
        if(rk != "-") r[i] = stoi(rk), has_father[stoi(rk)] = true;
    }
    int root = 0;
    while(has_father[root]) root++;
    dfs(root, 1);
    if (maxk == n) printf("YES %dn", maxid);
    else printf("NO %dn", root);
    return 0;
}

收获：

通过定义bool类型的数组has_father[]，来找到根节点