백준 2263 - 트리의 순회(트리 기초 순회이론, 완전탐색)

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

2263번: 트리의 순회

- 어떤 트리를 순회한다 할 때 inorder와 postorder가 주어졌을때 preorder를 구하는 문제이다

- 종만북에서 트리 기초파트를 설명할 때 나오는 TRAVERSAL 문제와 많이 흡사해서 참고하여 풀었다. 

- inorder와 postorder가 주어졌을 때 postorder의 마지막 노드가 트리의 루트인 점에서 부터 탐색을 시작한다. 

그리고 inorder를 기준으로 생각해보면 루트가 나오기 전까지는 왼쪽 부분트리이고 나온 후에는 오른쪽 부분트리이므로 부분트리의 크기가 0,1이 남을 때까지 가지치기 식으로 재귀를 돌리면 된다. preorder의 순서대로 루트 - 왼쪽트리 - 오른쪽트리 를 재귀로 basis까지 접근하여 출력하면 된다.

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

int in[100001];
int post[100001];
int idx[100001];

// pre 루-왼-오
// in 왼-루-오
// post 왼-오-루

// preorder 출력
void print(int inStart, int postStart, int size) {
    if (size == 0) return;
    if (size == 1) {
        cout << post[postStart] << ' ';
        return;
    }

    int root = post[postStart + size - 1];  // post 마지막 노드가 inorder root
    int rootIdx = idx[root];
    int leftSize = rootIdx - inStart;
    int rightSize = size - leftSize - 1;  // 전체 사이즈 - 왼쪽서브트리 - 루트 = 오른쪽서브트리

    cout << root << ' ';
    print(inStart, postStart, leftSize);
    print(rootIdx + 1, postStart + leftSize, rightSize);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int n;
    cin >> n;

    for (int i = 0; i < n; ++i) {
        cin >> in[i];
        idx[in[i]] = i;
    }
    for (int i = 0; i < n; ++i) {
        cin >> post[i];
    }

    print(0, 0, n);
    return 0;
}