[BOJ] 2263 - 트리의 순회 (C++)

문제

트리의 순회

코드

#include <iostream>

using namespace std;

int N;
int in[100001], post[100001], Index[100001];

void pre(int inStart, int inEnd, int postStart, int postEnd) {
    if (inStart > inEnd or postStart > postEnd) return;
    int root = Index[post[postEnd]];
    cout << in[root] << " ";

    pre(inStart, root-1, postStart, postStart+root-inStart-1);
    pre(root+1, inEnd, postStart+root-inStart, postEnd-1);
}

int main(void){
    cin.tie(0);
    ios_base::sync_with_stdio(false);

    cin >> N;

    for (int i = 1; i <= N; i++) { cin >> in[i]; Index[in[i]] = i; }
    for (int i = 1; i <= N; i++) cin >> post[i];

    pre(1, N, 1, N);
    return 0;
}

접근

솔직히 처음 접하자마자 풀기에 쉽지 않은 문제다. 이전에 리트코드에서 풀었던 기억이 있어 접근하는데 유리했다. 중위, 후위순회의 값을 알고 있기 때문에 우리는 어떤 노드가 루트 노드인지 알 수 있고 중위순회 값과 비교해 왼쪽, 오른쪽을 구별할 수가 있다. 따라서 살펴볼 범위를 인덱스로 제한하여 재귀호출하여 해결 할 수가 있었다.