PAT 堆中序序列生成树

满分

/**
题意:小根堆的中序序列,求层次遍历

核心: 就是找最小的点的位置即可

*/
#include <iostream>
#include <cstring>
#include <unordered_map>
#include <vector>
using namespace std;
const int N = 40, INF = 0x3f3f3f3f;
int l[N], r[N], in[N];
int build(int il, int ir)
{
    int mins = INF;
    int k = -1;
    for(int i = il; i <= ir; i++)
    {
        if (in[i] < mins)
        {
            mins = in[i];
            k = i;
        }
    }
    if (k > il) l[k] = build(il, k - 1);
    if (k < ir) r[k] = build(k + 1, ir);
    return k;
}
int main()
{
    int m;
    cin >> m;
    memset(l, -1, sizeof l);
    memset(r, -1, sizeof r);
    unordered_map<int, int> pos;
    for(int i = 0; i < m; i++) cin >> in[i], pos[i] = in[i];

    int root = build(0, m - 1);
    vector<int> res[m + 1];
    int cnt = 0;
    res[cnt].push_back(root);
    bool flag = true;
    while (!res[cnt].empty())
    {

        for(int i = 0; i < res[cnt].size(); i++)
        {
            int u = res[cnt][i];
            if (flag) flag = false;
            else printf(" ");
            printf("%d", pos[u]);
            if (l[u] != -1) res[cnt + 1].push_back(l[u]);
            if (r[u] != -1) res[cnt + 1].push_back(r[u]);
        }
        cnt++;
    }
}

满分

#include <iostream>
#include <cstring>
#include <unordered_map>
#include <queue>
using namespace std;

const int N = 40;
int l[N], r[N], in[N], p[N];
unordered_map<int,int> pos;
int max_num = 0x3f3f3f3f;
int m;
int first = 0;

int build (int il, int ir)
{
    // 先找最小,则为root
    int min = max_num;
    int root = -1, k = 0;
    for(int i = il; i <= ir; i++)
    {
        if (in[i] < min)
        {
            root = p[i];
            min = in[i];
            k = i;
        }
    }
    if (k > il) l[root] = build(il, k - 1);
    if (k < ir) r[root] = build(k + 1, ir);
    return root;
}
void level(int root)
{
    bool flag = true;
    queue<int> q;
    q.push(pos[root]);
    while(!q.empty())
    {
        int front = q.front();

        if (flag) flag = false;
        else printf(" ");
        printf("%d", in[front]);
        q.pop();
        if (l[front] != -1) q.push(l[front]);
        if (r[front] != -1) q.push(r[front]);
    }
}
int main()
{
    memset(l, -1, sizeof l);
    memset(r, -1, sizeof r);
    cin >> m;
    for(int i = 0; i < m; i++)
    {
        cin >> in[i];
        p[i] = in[i];
        pos[in[i]] = i;
    }
    for(int i = 0; i < m; i++) p[i] = pos[p[i]];
    build (0, m - 1);
    first = max_num;
    for(int i = 0; i < m; i++)
    {
        if (in[i] < first) first = in[i];
    }
    // 中序
    level(first);
}