[Algospot] 알고스팟 TRAVERSAL 트리 순회 순서 변경

출처: https://algospot.com/judge/problem/read/TRAVERSAL

 Input 

2

7

27 16 9 12 54 36 72

9 12 16 27 36 54 72

6

409 479 10 838 150 441

409 10 479 150 838 441

 

 Output 

12 9 16 36 72 54 27

10 150 441 838 479 409

 

① 트리의 Root Node는 전위순회(PreOrder)의 첫번째 원소입니다.

    ▶ preorder = [27 16 9 12 54 36 72]

② 중위 순회(inorder)에서 루트 노드를 찾습니다.

    ▶ 9 12 16 27 36 54 72

    루트를 기준으로 왼쪽 서브 트리 / 오른쪽 서브 트리 구분 가능.

    후위순회: 왼쪽 서브 트리 → 오른쪽 서브 트리 → 중간(루트) 

    후위순회에서는 [9 12 16] → [36 54 72] → 27 분류할 수 있습니다.

    즉, 왼쪽/오른쪽 서브트리에 대해 재귀적으로 루트와 왼쪽/오른쪽 서브트리를 구해갑니다.

 

③ 왼쪽 서브트리 [9 12 16]에서 루트노드에 해당하는 노드는 전위순회에서 알 수 있습니다.

    preorder = [27 16 9 12 54 36 72] 이므로, 16 입니다.

    [9 12 16]에서 [9 12]가 16의 왼쪽 서브트리입니다. (오른쪽 서브트리 존재 X)

 

④ 서브트리 [9 12]에서 중간(루트)노드는 초기 전위 순회에서 알 수 있습니다.

    preorder = [27 16 9 12 54 36 72] 이므로, 9입니다.

    [9 12]에서 [12]가 9의 오른쪽 서브트리에 해당됩니다.

 

⑤ 이러한 과정을 왼쪽/오른쪽 서브트리가 존재하지 않을때까지 재귀적으로 진행한 다음,

    중간(루트)에 해당되는 노드를 출력하며 됩니다.

    결과적으로 전체 트리의 루트 노드는 제일 마지막에 출력됩니다.

 

 

재귀탐색 과정에서 루트의 위치가 L이라면

- (왼쪽 서브트리) 전위 순회는 1 ~ (L+1)이고, 중위 순회는 0 ~ L

- (오른쪽 서브트리) 전위 순회는 (L+1) ~ N이고, 중위 순회는 (L+1) ~ N

---

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>

using namespace std;

vector<int> slice(const vector<int>& v, int a, int b) {
    return vector<int>(v.begin() + a, v.begin() + b);
}

void printPostOrder(const vector<int>& preorder, const vector<int>& inorder) {
    if (preorder.empty()) return;
    const int N = preorder.size();
    const int root = preorder[0];
    const int L = find(inorder.begin(), inorder.end(), root) - inorder.begin();
    const int R = N - 1 - L;

    // 왼쪽 서브트리에 해당하는 구간을 전위순회와 중위순회에서 찾아서 매개변수로 전달
    printPostOrder(slice(preorder, 1, L + 1), slice(inorder, 0, L));
    // 오른쪽 서브트리에 해당하는 구간을 전위순회와 중위순회에서 찾아서 매개변수로 전달
    printPostOrder(slice(preorder, L + 1, N), slice(inorder, L + 1, N));
    cout << root << " ";
    return;
}

int main() {
    int C;
    cin >> C;
    while (C--) {
        int N;
        cin >> N;
        
        vector<int> preorder, inorder;
        int node;
        // 전위 순회
        for (int i = 0; i < N; i++){
            cin >> node;
            preorder.push_back(node);
        }

        for (int i = 0; i < N; i++){
            cin >> node;
            inorder.push_back(node);
        }

        printPostOrder(preorder, inorder);
        cout << endl;
    }
}