[백준] 4256 트리

트리의 전위,중위 순회 결과를 주고 후위 순회 결과를 구하는 문제다

재귀를 잘 이용하면 풀 수 있다

방법은

1. 전위순회에서 첫번째 노드는 루트라는것을 기억한다!

2. 후위순회에서 루트기준 앞쪽 노드들은 왼쪽, 뒷쪽은 오른쪽 서브트리다

3. 후위 순회를 출력하므로 왼쪽 오른쪽 순서로 함수를 호출하고 루트를 출력한다

후위순회에서 루트 위치를 찾기 위해 map을 사용했다!

소스코드

#include <iostream>
#include <algorithm>
#include <map>
#include <cstring>
using namespace std;
int t, n, pre[1010], in[1010];
map<int, int> mp;
 
void go(int s, int e,int x, int y) {
 
    if (s > e || x > y) return;
 
    int root = pre[s];
    int pos = mp[pre[s]];
 
    go(s + 1, s + (pos - x), x, pos - 1);
    go(s + (pos - x) + 1, e, pos + 1, y);
    printf("%d ", root);
}
int main() {
    scanf(" %d", &t);
    while (t--) {
        memset(pre, 0, sizeof(pre));
        mp.clear();
        scanf(" %d", &n);
        for (int i = 0; i < n; i++) scanf(" %d", &pre[i]);
        for (int i = 0; i < n; i++) {
            int x; scanf(" %d", &x);
            in[i] = x;
            mp[x] = i;
        }
        go(0, n - 1, 0, n - 1); puts("");
    }
}