[백준][C++] 2263번: 트리의 순회 <191>

직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다.

2263번: 트리의 순회

 

생각의 흐름

이진 트리의 인오더와 포스트오더가 주어졌을 때, 프리오더를 구해야 하는 문제이다.

 

다음 이진트리를 우선 살펴보자.

• 중위 순회 : 8 4 9 2 5 1 6 3 7
• 후위 순회 : 8 9 4 5 2 6 7 3 1

우리는 후위 순회를 통해 root 번호를 알수가 있다.

후위 순회의 마지먹 번호인 1이 root에 해당된다.

이렇게 root를 알게되면, 중위 순회를 통하여 이진트리를 좌 우 로 나눌수가 있다.

중위 순회는 root인 1을 기준으로 왼쪽의 (8 4 9 2 5) 와 오른쪽의 (6 3 7) 로 나눌수가 있다.

왼쪽의 (8 4 9 2 5) 는 이들간의 순서는 몰라도 1보다 왼쪽에 있다는 것 은 확실하다.

오른쪽의 (6 3 7) 은 이들간의 순서는 몰라도  1보다 오른쪽에 있다는 것 은 확실하다.

 

다시 재귀적으로 왼쪽의 (8 4 9 2 5) 를 살펴보자, 후위 순회를 보니 8 9 4 5 2 이니 (8 4 9 2 5) 에서의 root는 2가 된다.

즉, 8 4 9 2 5 에서 2가 root이고, 849는 왼쪽, 5는 오른쪽에 배치하게 된다.

 

즉 이런식으로 재귀적으로 계속 후위 순회의 마지막 수를 확인하면서 진행하면 된다.

void recur(int inStart, int inEnd, int postStart, int postEnd){
    // 생략

    recur(inStart, rootIndex-1, postStart, postStart+leftLen-1);
    recur(rootIndex+1, inEnd, postEnd-rightLen, postEnd-1);
}

recur로 다시 전달되는 인자는 다음 그림과 같다.

나의 코드

#include <bits/stdc++.h>
using namespace std;
#define MAX 100001

int n, rootIndex;
int in[MAX];
int post[MAX];
int Index[MAX];

void recur(int inStart, int inEnd, int postStart, int postEnd){
    // 탈출 조건
    if (inStart > inEnd || postStart > postEnd) {
        return;
    }

    int rootIndex = Index[post[postEnd]];
    int leftLen = rootIndex - inStart;
    int rightLen = inEnd - rootIndex;
    cout << in[rootIndex] << " ";

    recur(inStart, rootIndex-1, postStart, postStart+leftLen-1);
    recur(rootIndex+1, inEnd, postEnd-rightLen, postEnd-1);
}


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

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

    recur(0, n-1, 0, n-1);

    return 0;
}