PAT 1115. Counting Nodes in a BST(30)(二叉探索木の挿入)

題意:空のBSTを順番に挿入した後、最後の2階のノードの数の和はいくらですか.
構想:二叉探索ツリーの挿入をシミュレートし,lchとrchはそれぞれ左右の子供の動的開点を記録し,またval配列を開いて各ノードの値を記録する.
コード:

#include
#include
#include
#include
#include
using namespace std;
const int maxn = 1e5+5;
int lch[maxn], rch[maxn], val[maxn], n;
int lev[maxn];
struct node
{
    int x, l;
    node(){}
    node(int xx, int ll): x(xx), l(ll) {}
};

void solve()
{
    memset(lev, 0, sizeof(lev));
    queue q;
    q.push(node(0, 1));
    node u;
    while(!q.empty())
    {
        u = q.front(); q.pop();
        lev[u.l]++;
        if(lch[u.x] != -1) q.push(node(lch[u.x], u.l+1));
        if(rch[u.x] != -1) q.push(node(rch[u.x], u.l+1));
    }
    printf("%d + %d = %d
", lev[u.l], lev[u.l-1], lev[u.l]+lev[u.l-1]);
}

int main(void)
{
    while(cin >> n)
    {
        memset(lch, -1, sizeof(lch));
        memset(rch, -1, sizeof(rch));
        int cur = 0;
        int x;
        scanf("%d", &x);
        val[cur++] = x;
        for(int i = 2; i <= n; i++)
        {
            scanf("%d", &x);
            int tmp = 0;
            while(1)
            {
                if(x <= val[tmp])
                {
                    if(lch[tmp] == -1)
                    {
                        lch[tmp] = cur;
                        val[cur++] = x;
                        break;
                    }
                    else
                        tmp = lch[tmp];
                }
                else
                {
                    if(rch[tmp] == -1)
                    {
                        rch[tmp] = cur;
                        val[cur++] = x;
                        break;
                    }
                    else
                        tmp = rch[tmp];
                }
            }
        }
        solve();
    }
    return 0;
}