1110. Complete Binary Tree (25)

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

struct node { int ad, l, r; };
vector<bool> visited(20, false);
vector<node> nodes;
int n,root = 0;

int main(){
    cin >> n;
    nodes.resize(n);
    for (int i = 0; i < n; i++) {
        string l, r;
        cin >> l >> r;
        if(l != "-"){
            nodes[i].l = stoi(l);
            visited[stoi(l)] = true;
        }else nodes[i].l = -1;
        if(r != "-"){
            nodes[i].r = stoi(r);
            visited[stoi(r)] = true;
        }else nodes[i].r = -1;
    }
    for(int i = 0; i < n; i++)
        if(visited[i] == 0) { root = i; break; }

    //层序遍历的思想
    queue<int> q;
    q.push(root);
    int cnt = 0;
    int lastnode = 0;
    while (!q.empty()) {
        int node = q.front();
        q.pop();
        if (node != -1) {
            lastnode = node;
            cnt++;
        }else{
            if(cnt != n)
                printf("NO %d\n", root);
            else
                printf("YES %d\n", lastnode);
            return 0;
        }
        q.push(nodes[node].l);
        q.push(nodes[node].r);
    }

    return 0;
}