백준 2263, 트리의 순회(C, C++)

 

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

위 그림으로 예시를 들어보자.

전위 순회를 했을 경우

1 2 3 4 5 6 7

중위 순회를 했을 경우

3 2 4 1 6 5 7

후위 순회를 했을 경우

3 4 2 6 7 5 1

 

중위 순회를 배열로 나타냈을 경우 root의 위치는 가운데에 있다.

1을 기준으로 왼쪽을 바라봤을 때 3 2 4는 가운데 2를 부모노드로 다시 한 번 왼쪽과 오른쪽을 나누고있다

1을 기준으로 오른쪽을 바라봤을 때 5가 부모노드이며 왼쪽과 오른쪽을 나눈다.

후위 순회를 배열로 나타낸 경우에는 루트가 마지막 인덱스에 자리잡고 있다.

왼쪽은 다시 한번 2가 루트노드가 될 것이고

오른쪽은 5가 루트노드가 될 것이다.

마지막 인덱스가 루트노드인 것을 이용하여 코드를 짜보도록 하자.

 

#include<iostream>

using namespace std;
int inorder[100001];
int postorder[100001];
int index[100001];

void preorder(int inorder_start, int inoredr_end, int post_start, int post_end){
    if(inorder_start > inoredr_end || post_start > post_end){
        return;
    }
    int root = postorder[post_end];
    cout<<root<<' ';
    int inorder_location = index[root]; // 인오더에서 루트의 위치
    int jump = inorder_location - inorder_start;
    //왼쪽
    preorder(inorder_start, inorder_location-1, post_start, post_start + jump-1);
    //오른쪽
    preorder(inorder_location+1, inoredr_end, post_start+jump, post_end-1);
}

int main(){
    int N;
    cin >> N;

    for(int i = 0; i < N; i++){
        cin >> inorder[i];

    }
    for(int i = 0; i < N; i++){
        cin>>postorder[i];
    }
    for(int i = 0; i < N; i++){
        index[inorder[i]] = i;
    }
    preorder(0, N-1, 0, N-1);
    return 0;
}