TRAVERSAL

AOJ TRAVERSAL

SOL)

전위 순회의 맨 앞은 root라는 특성과 중위 순회의 root를 기준으로 왼쪽과 오른쪽이 나뉘는
특성을 이용하여야 한다.

preorder[0]은 항상 root
root의 값을 inorder에서 찾는다.
inorder에서 root를 기준으로 왼쪽의 값들은 왼쪽에 있는 것이고
오른쪽의 값들은 오른쪽에 있는것이다.
이를 이용하여 재귀적으로 배열을 분할하여 출력을 한다.

[-] Collapse

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

vector<int> slice(const vector<int>& v, int a, int b) {
    return vector<int>(v.begin() + a, v.begin() + b);
}

void printPost(const vector<int>& preorder, const vector<int>& inorder){
    if (preorder.empty()) return;
    int root = preorder[0];
    int L = find(inorder.begin(), inorder.end(), root) - inorder.begin();
    int N = preorder.size();
    printPost(slice(preorder, 1, L + 1), slice(inorder, 0, L));
    printPost(slice(preorder, L + 1, N), slice(inorder, L + 1, N));
    printf("%d ", root);
}

int main(){
    int t; scanf("%d", &t);
    while (t--){
        int n; scanf("%d", &n);
        vector<int> pre(n), inor(n);
        for (int i = 0; i < n; i++)
            scanf("%d", &pre[i]);
        for (int i = 0; i < n; i++)
            scanf("%d", &inor[i]);
        printPost(pre, inor);
        puts("");
    }
}