BOJ 2263 - 트리의 순회

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

n개의 정점을 갖는 이진 트리의 정점에 1부터 n까지의 번호가 중복 없이 매겨져 있다.
이와 같은 이진 트리의 인오더와 포스트오더가 주어졌을 때, 프리오더를 구하는 프로그램을 작성하시오.

Solution

우선 각 순회들의 전반적인 순서를 살펴보자면
pre : root L R
in : L root R
post : L R root

순으로 방문하게 된다.

예시를 들어보자.
input 으로 1,2,3,4,5가 들어왔을때

Inorder

4	2	5	1	3

Postorder

4	5	2	3	1

과 같다.

여기서 Postorder 는 순서가 LR root 순으로 방문하기 때문에 마지막 값인 '1'이 root노드인것을 알 수 있다. 그리고 1 전으로 왼쪽자식, 오른쪽 자식임을 알 수 있다.

문제는 어디까지가 왼쪽자식이며 오른쪽 자식임을 알 수 없기에, 이때 Inorder 방문순서를 활용하게 된다.
왜냐면 Inorder는 L root R 순으로 방문하기 때문에 root노드의 위치를 알게된다면 그 위치를 기준으로 왼쪽자식과 오른쪽 자식을 나눌수 있다.

(root 1을 기준으로 4 2 5 가 왼쪽 자식, 3이 오른쪽 자식)

왼쪽자식과 오른쪽자식으로 나누었다면, 새롭게 나뉜 배열에서 다시 root를 찾고, 과정을 반복한다.

정답으로 출력해야할 Preorder는 root부터 방문하기 때문에 위 과정에서 root를 찾을시 바로바로 출력해주면 정답을 찾을 수 있다.

시간복잡도를 알아보자면 O(N^2) 인데 정점의 개수가 N개이며 Inorder 배열에서 root노드를 찾는데 또 N의 시간이 걸리기 때문이다.

그런데 N으로 들어올수 있는 최대값은 10만이기에 주어진 시간안에 문제를 해결할 수 없다. 그렇기 때문에 또다른 배열에 Inorder의 위치를 저장해주어서 O(N)으로 문제를 해결할 수 있다.

Code

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

int inorder[MAXV];
int postorder[MAXV];
int position[MAXV];

//파라미터로 inorder의 시작점, 끝점 / postorder의 시작점, 끝점 인덱스를 받는다.
void solve(int in_start, int in_end, int post_start, int post_end) {
    if (in_start > in_end || post_start > post_end) return;
    int root = postorder[post_end];
    cout << root << ' ';
    int p = position[root]; //inorder에서 root의 index를 바로 찾음! O(1)

    int left = p - in_start;

    //왼쪽, 오른쪽으로 나뉘어서 재귀적으로 실행
    solve(in_start, p - 1, post_start, post_start + left - 1);
    solve(p + 1, in_end, post_start + left, post_end - 1);
}

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

    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++)
        position[inorder[i]] = i;

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

    return 0;
}

위에서 Position이 inorder의 위치를 저장하고 있는 배열이 된다.
예를들어 root 값이 1이라고 했을시

4	2	5	1	3

position[inorder[3]] = position[1] = 3 으로 저장되기에 즉각적으로 값을 찾을 수 있다.
이 정보를 활용하여 Inorder배열에서 좌, 우 자식을 분류할 수 있다.



참고 : https://code.plus/course/43 , 분할 정복(연습)