2263번: 트리의 순회

https://www.acmicpc.net/problem/2263


$O(n)$

인오더 수열 ai
포스트오더 수열 bi

f(al,ar,bl,br): ai는 [l,r], bi는 [l,r]을 보고 있다고 하자.
br은 현재보고 있는 수열 중 루트임을 알 수 있다.
또한 br과 같은 ax 좌, 우에 있는 항들로 서브트리가 갈라짐을 알 수 있다.
여기서 좌, 우 서브트리의 자식 노드 개수를 알 수 있고 이를 이용해 bi의 항들을 나눠 f를 호출한다.

#include<cstdio>
const int MXN = 1e5;
int n, b[MXN], ai[MXN + 1];
void f(int al, int ar, int bl, int br) {
    if (bl > br) return;
    printf("%d ", b[br]);
    f(al, ai[b[br]] - 1, bl, ai[b[br]] - 1 - al + bl);
    f(ai[b[br]] + 1, ar, br - ar + ai[b[br]], br - 1);
}
int main() {
    scanf("%d", &n);
    for (int i = 0, x; i < n; i++) scanf("%d", &x), ai[x] = i;
    for (int i = 0; i < n; i++) scanf("%d", b + i);
    f(0, n - 1, 0, n - 1);
    return 0;
}