BOJ 2263 트리의 순회

📝 문제 정보

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

🧐 관찰 및 접근

이진 트리의 인오더와 포스트오더가 주어졌을 때, 프리오더를 구하자.
- 인오더: (왼쪽 -> 루트 -> 오른쪽)
- 포스트오더: (왼쪽 -> 오른쪽 -> 루트)
- 프리오더: (루트 -> 왼쪽 -> 오른쪽)
그렇다면, 어떤 한 서브트리에 대해, 포스트오더를 이용해서 루트를 찾을 수 있다. (맨 마지막 값)
- 그리고 이를 기점으로 인오더에서 왼쪽에 있는 모든 수는 왼쪽 서브트리, 나머지는 오른쪽 서브트리에 있다고 생각할 수 있다.
한 서브트리에서 루트노드의 값을 알아냈을 때, 인오더에서의 그 인덱스를 빠르게 찾을 수 있다면 왼쪽/오른쪽 서브트리로의 분할이 용이하다!
- map을 이용하면 $O(NlogN)$에 해결할 수 있겠다.

💻 풀이

코드 (C++):

int N;
vector<int> inorder, postorder;
map<int, int> in_idx;

void preorder(int in_s, int in_e, int post_s, int post_e){
    if(in_s > in_e) return;
    int root = postorder[post_e];
    cout << root << ' ';
    int idx = in_idx[root];
    int sz = idx - in_s;
    preorder(in_s, idx-1, post_s, post_s + sz - 1); // 왼쪽 서브트리
    preorder(idx+1, in_e, post_s + sz, post_e - 1); // 오른쪽 서브트리
}

void solve(){
    cin >> N;
    inorder.resize(N);
    postorder.resize(N);
    rep(i, 0, N) cin >> inorder[i];
    rep(i, 0, N) cin >> postorder[i];
    rep(i, 0, N) in_idx[inorder[i]] = i;

    preorder(0, N-1, 0, N-1);
}