[백준 2263번 | C++] 트리의 순회

출처: 트리의 순회

문제

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

입력

첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다.

출력

첫째 줄에 프리오더를 출력한다.

풀이

트리 구조 순회 알고리듬 종류가 여러가지 있는데 대표적으로 BFS, DFS가 있다.
DFS에서 Inorder, Preorder, Postorder Traversal 알고리듬이 있다.
이 문제를 풀기 위해 이를 먼저 숙지해야 한다.

참고: Inorder, Preorder, Postorder Traversal 설명

문제 예제 입력이 매우 불친절해서 필자가 예제 입력을 추가해 보겠다.

7
4 2 5 1 6 3 7
4 5 2 6 7 3 1

핵심은 'root를 어떻게 구하는가?' 이다.

        root
Inorder   v
+-------------------+
| 4 2 5 | 1 | 6 3 7 |
+-------------------+
                 root
Postorder          v
+-------------------+
| 4 5 2 | 6 7 3 | 1 |
+-------------------+

Inorder traversal은 3번 index가 root이고,
Postorder traversal은 6번 index가 root이다.

Postorder 성질상 맨 뒤에 있는 값이 root이다.
그러면 Postorder 벡터에서 root를 찾고, Inorder 벡터에서 left subtree와 right subtree를 알 수 있다.

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

int root = postorder[postRight];
int root_index = position[root];

다음과 같이 inorder 벡터의 index를 position 벡터에 저장하면 postorder 벡터에서 root 값을 찾으면,
바로 inorder 벡터에서 root 위치를 찾을 수 있다.

이를 활용해 inorder left와 right를 계산하고,
postorder left와 right를 계산해서 재귀함수로 해결하면 된다.

void solve(int inLeft, int inRight, int postLeft, int postRight) {
    if (inLeft > inRight || postLeft > postRight) return;

    int root = postorder[postRight];
    cout << root << ' ';

    int root_index = position[root];
    int left_size = root_index - inLeft;
    // cout << left_size;

    // left
    solve(inLeft, root_index-1, postLeft, postLeft + left_size - 1);

    // right
    solve(root_index+1, inRight, postLeft + left_size, postRight-1);
}

코드

// 2263
#include <iostream>
#include <vector>
using namespace std;

vector<int> inorder, postorder, position, preorder;

void solve(int inLeft, int inRight, int postLeft, int postRight) {
    if (inLeft > inRight || postLeft > postRight) return;

    int root = postorder[postRight];
    cout << root << ' ';

    int root_index = position[root];
    int left_size = root_index - inLeft;
    // cout << left_size;

    // left
    solve(inLeft, root_index-1, postLeft, postLeft + left_size - 1);

    // right
    solve(root_index+1, inRight, postLeft + left_size, postRight-1);
}

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

    inorder.resize(n);
    postorder.resize(n);
    position.resize(n+1);
    preorder.resize(n);

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

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

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

    return 0;
}