[백준 4256번] [트리] 트리

Approach

자료구조 수업에서나 나올법한 문제이다. 잘 생각해보면 preorder가 하는 역할을 잘 생각해보면, 루트 노트부터 시작해서 왼쪽 방향무터 서브트리의 루트노드를 지속적으로 방문하게 된다. 따라서 해당 순서를 inorder에서 바라보게 되면, 발견한 index를 기준으로 왼쪽은 자신을 기준으로 왼쪽과 오른쪽으로 subtree를 나누어서 생각할 수 있다. 세그트리 짜는 것처럼, start, end index를 함수의 입력값으로 두고 계속해서 좁혀가면 쉽게 구할 수 있다.

Code

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0). cin.tie(0), cout.tie(0)

using namespace std;

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

void find(int left, int right){
    
    int cur = preorder[index_val++];
    int index;

    if (left == right)
    {
        cout << cur << " ";
        return;
    }
    else if(left > right){
        index_val--;
        return;
    }

    for(int i = left; i <= right; i++){
        if(inorder[i] == cur){
            index = i;
            break;
        }
    }

    find(left, index - 1);
    find(index + 1, right);
    cout << cur << " ";
    return;
}

int main(void){
    int t;
    cin >> t;
    while(t--){
        index_val = 0;
        int n;
        cin >> n;
        preorder = vector<int>(n);
        inorder = vector<int>(n);

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

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

        find(0, n - 1);
        cout << "\n";
    }
    return 0;
}