백준 4256 트리

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

4256번: 트리

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

using namespace std;

vector<int> preorder;
vector<int> inorder;


void divide(int s, int e, int root){

    for (int i = s; i < e; i++) {
        if (inorder[i] == preorder[root]) {
            divide(s, i, root + 1);
            divide(i + 1, e, root + 1 + i - s);
            cout << preorder[root] << " ";
        }
    }


}

int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int t;
    cin >> t;


    for (int test = 0; test < t; test++) {

        int n;

        cin >> n;

        preorder.clear();
        inorder.clear();

        preorder.resize(n);
        inorder.resize(n);

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

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

        divide(0, n, 0);
        cout << "\n";

    }

    return 0;
}

 

preorder 연산은 루트 좌 우 순이므로 해당 순서의 가장 첫 번째 노드가 루트 노드이다.

이를 inorder를 돌면서 찾으면 좌측 노드와 우측 노드로 나눌 수 있다.

 

- 좌측 노드: 맨 앞의 노드는 현재 연산의 루트노드 이므로 그 다음에 나오는 노드가 좌측 연산의 루트 노드가 된다.

- 우측 노드: root는 preorder의 root의 좌표이다. 우측 노드의 루트를 표현하려면 현재 연산의 루트노드, 좌측의 모든 노드가 모두 나온 다음 우측 연산의 루트 노드가 나온다.

 

 

해당 연산을 반복하여 후위 연산을 구현한다.