PAT A1110 Complete Binary Tree [完全二叉树]

#include<bits/stdc++.h>
using namespace std;

const int maxn = 20;
struct node{
    int l,r;
}nodes[maxn];

int n, have[maxn], rt;
string l,r;
int maxid = -1, ans;
void dfs(int root, int idx){
    if(root == -1) return;
    if(idx > maxid){
        maxid = idx;
        ans = root;
    }
    dfs(nodes[root].l, idx * 2);
    dfs(nodes[root].r, idx * 2 + 1);
}

int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>l>>r;
        if(l == "-") nodes[i].l = -1;
        else{
            nodes[i].l = stoi(l);
            have[nodes[i].l] = 1;
        }
        if(r == "-")nodes[i].r = -1;
        else{
            nodes[i].r = stoi(r); //stoi函数
            have[nodes[i].r] = 1; //标记
        }
    }
    while(have[rt]==1) rt++;  //寻找根结点
    dfs(rt, 1);
    if(maxid == n) printf("YES %d
",ans);
    else printf("NO %d
", rt);

}