BOJ 2263 트리의 순회(풀이, C++)

2263번 트리의 순회 문제는 이진 트리의 순회에 관한 문제로, 이진 트리의 중위 순회(In-order traversal)와 후위 순회(Post-order traversal)를 받아 전위 순회(Pre-order traversal)를 출력하는 문제입니다.

풀이

예시 이진 트리

이해를 돕기 위해 위의 이진 트리를 보겠습니다. 해당 트리의 순회 순서는 다음과 같습니다.

중위 순회: 8 -> 4 -> 2 -> 9 -> 5 -> 10 -> 1 -> 11 -> 6 -> 3 -> 12 -> 7

후위 순회: 8 -> 4 -> 9 -> 10 -> 5 -> 2 -> 11 -> 6 -> 12 -> 7 -> 3 -> 1

전위 순회: 1 -> 2 -> 4 -> 8 -> 5 -> 9 -> 10 -> 3 -> 6 -> 11 -> 7 -> 12

 

우선 저희가 구해야 할 것은 전위 순회입니다. 전위 순회는 먼저 부모 노드를 먼저 탐색하고 자식 노드를 순회하기에 재귀적으로 만들기 쉽습니다. 이때 후위 순회는 그 특성상 마지막에 부모 노드가 오게 되어있습니다. 이를 이용한다면 전위 순회를 찾아낼 수 있을 것 같습니다.

다음과 같은 방식으로 후위 순회의 마지막이 1인 것을 이용해 첫 부모 노드가 1인 것을 알 수 있습니다. 그리고 중위 순회의 특성상 중위 순회는 왼쪽 자식노드 -> 부모 노드 -> 오른쪽 자식 노드를 탐색하기에 중위 순회에서 부모 노드의 위치를 찾아낸다면 그 왼쪽에 있는 노드들은 왼쪽 자식 노드에 속하고 오른쪽에 있는 노드들은 오른쪽 자식 노드에 속함을 알 수 있습니다.

그렇다면 이 왼쪽, 오른쪽 자식 노드들을 후위 순회에서 찾아, 후위 순회에서 가장 오른쪽이 부모 노드임을 이용한다면, 다시 부모 노드를 찾아낼 수 있을 것입니다.

 

자 여기까지 찾아냈다면 알고리즘은 간단합니다. 이를 재귀적으로 이용하여 풀어낼 수 있을 것 같습니다.

 

1. 후위 순회의 가장 오른쪽에 부모 노드가 위치함을 이용해 부모 노드를 찾는다.

2. 찾아낸 부모 노드를 중위 순회에서 탐색 -> 찾은 부모 노드 왼쪽에 위치한 노드(왼쪽 자식 노드)들을 탐색 -> 찾은 부모 노드 오른쪽에 위치한 노드(오른쪽 자식 노드)들을 탐색, 과정을 거친다면 전위 순회 찾을 수 있을 것입니다.

 

그렇다면 이 과정을 거치면 실제로 어떻게 진행되는지 보겠습니다.

과정 1

후위 순회 오른쪽에서 1을 찾고, 중위 순회에서 1의 위치를 찾아 왼쪽 값들을 다시 탐색해 나갑니다.

과정 2

좌측 값들 중에서 다시 부모 노드를 찾아내어 진행합니다.

과정 3

과정 4

이제 더 이상 쪼개지지 않는 부분까지 온 것 같습니다. 이를 기저사례로 하여도 문제가 없을 것입니다.

여기서 마지막 8을 출력한 후 8을 부모 노드로 하는 자식 노드는 없기에 조건을 달아 return을 시작해 주면 될 것입니다.

 

조건 1. 만약 범위의 시작 위치와 마지막 위치가 같다면 더 이상 탐색을 중단하고 return 한다.

 

하지만 이렇게만 조건을 단다면 문제가 생길 수 있습니다. 이는 다음 과정에서 볼 수 있습니다. 4를 기준으로 왼쪽 노드 탐색을 통하여 8은 찾아내었지만 오른쪽 노드는 범위가 존재하지 않습니다.

과정 5

이를 방지하기 위해서는 자식 노드를 탐색할 때 범위가 0이라면 아예 탐색을 하지 않는 방식으로도 구현할 수 있고, 아니면 탐색을 실시하지만 범위가 0이라면 출력하지 않고 바로 return을 시도하는 방식으로도 구현이 가능합니다.

 

조건 2. 만약 범위가 0이라면 출력 없이 바로 return 한다.

 

위의 알고리즘을 적용시킨 것이 아래 코드입니다.

C++ 코드

#include <iostream>
using namespace std;

int n;
int inOrder[100001];
int postOrder[100001];

void traversal(int inStart, int inEnd, int postStart, int postEnd) {
    int root = postOrder[postEnd]; // 부모 노드의 값 찾기
    if (inStart > inEnd) // 조건 2. 범위가 0이여서 inStart가 더 커질시 출력 없이 return
        return;
    cout << root << " "; // 부모 노드의 값 출력
    if (inStart == inEnd) // 조건 1. 만약 범위가 1이라면 출력후 바로 return
        return;

    int locate = -1;
    for (int i = inStart; i <= inEnd; i++) { // 중위 순회에서 부모 노드의 위치 찾기
        if (inOrder[i] == root) {
            locate = i;
            break;
        }
    }
    int size = locate - inStart; // 왼쪽 노드들의 개수
    traversal(inStart, inStart + size - 1, postStart, postStart + size - 1); // 왼쪽 노드 탐색
    traversal(inStart + size + 1, inEnd, postStart + size, postEnd - 1); // 오른쪽 노드 탐색
}

int main() {
    // Input
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> inOrder[i];
    for (int i = 1; i <= n; i++)
        cin >> postOrder[i];

    traversal(1, n, 1, n);

중위 순회의 범위를 알려주는 inStart, inEnd를 전달하고, 후위 순회의 범위를 알려주는 postStart, postEnd도 전달해 주었습니다.