1110 Complete Binary Tree（25 分）

#include <iostream>
#include <string>
#include <map>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
#define STP system("pause")


struct node
{
    int left, right;
};


int main()
{
    int M,a,Nroot;
    cin >> M;
    vector<node> v(M);
    vector<int> root(M);

    for (int i = 0; i < M; i++)
    {
        string l, r;
        cin >> l >> r;

        if (l == "-")//排除左右的非数值
            v[i].left = -1;
        else
        {
            v[i].left = stoi(l);
            root[v[i].left] = 1;
        }

        if (r == "-")
            v[i].right = -1;
        else
        {
            v[i].right = stoi(r);
            root[v[i].right] = 1;
        }
    }
    
    for (int i = 0; i < root.size(); i++)
    {
        if (root[i] == 0)
        {
            Nroot = i;
            break;//此时即可求得根节点
        }
    }


    /*开始进行广度优先搜索*/
    queue<int> qn;
    qn.push(Nroot);//设置初始压入的节点
    int cnt = 0;
    int num_before = 0;
    while (!qn.empty())
    {
        int num = qn.front();
        qn.pop();//移出队列
        if (num!=-1)
        {
            cnt++;//统计在一颗树上的节点总数
            num_before = num;
        }
        else
        {
            if (cnt==M)//是的
            {
                cout << "YES " << num_before << endl;
            }
            else
            {
                cout << "NO " << Nroot << endl;
            }
            STP;
            return 0;
        }
        qn.push(v[num].left);//压入左侧的元素
        qn.push(v[num].right);//压入右侧的元素
    }

    STP;
    return 0;
}