【甲级1127另解】参考柳神甲级1020的实现

[Vanffer]

建树过程中记录层号和序号，按照层号序号排序，排序后的数组即为Z字形遍历的结果

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

struct node{
    int id;
    int value;
    int layer;
};

vector<int> post, in;
vector<node> level;

bool cmp(node &a, node &b){
    if(a.layer == b.layer){
        if(a.layer % 2 == 0){
            return a.id > b.id;
        }else{
            return a.id < b.id;
        }
    }
    return a.layer < b.layer;
}

void build(int root, int left, int right, int index, int layer){
    if(left > right) return;
    int middle = left;
    while(middle < right && post[root] != in[middle]) middle++;
    // cout << index << " " << in[middle] << " " << layer << endl;
    level.push_back({index, in[middle], layer});
    build(root - (right - middle + 1), left, middle - 1, 2 * index + 1, layer + 1);
    build(root - 1, middle + 1, right, 2 * index + 2, layer + 1);
}

int main(){
    int n;
    cin >> n;
    int num;
    for(int i = 0; i < n; ++i){
        cin >> num;
        in.push_back(num);
    }
    for(int i = 0; i < n; ++i){
        cin >> num;
        post.push_back(num);
    }
    build(n - 1, 0, n - 1, 0, 0);
    sort(level.begin(), level.end(), cmp);
    cout << level[0].value;
    for(int i = 1; i < n; ++i) cout << " " << level[i].value;
    return 0;
}