4256 트리

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

4256번: 트리

트리의 순회마냥 분할 정복으로 해결이 가능하다. 비슷한 유형이라 해결하는데 큰 어려움은 없었다. 

#include<bits/stdc++.h>
using namespace std;

int preorder[1003];
int inorder[1003];
int inidx[1003]; //inorder에서 특정 원소의 idx 저장

void postorder(int pre_S, int pre_E, int in_S, int in_E){
    if(pre_S>pre_E || in_S>in_E) return;
    int root = preorder[pre_S]; //root의 값
    int root_idx = inidx[root]; //inorder 배열에서의 root 번호
    int l_size = root_idx - in_S; //inorder에서 root 기준 왼쪽 값 갯수
    postorder(pre_S+1,pre_S+l_size,in_S,root_idx-1);
    postorder(pre_S+l_size+1,pre_E,root_idx+1,in_E);
    cout<<root<<' ';
}

int main(){
    ios::sync_with_stdio(0);
    //cin.tie(0); cout.tie(0);
    int t; cin>>t;  
    while(t--){
        int n; cin>>n;
        fill(preorder,preorder+n+1,0);
        fill(inorder,inorder+n+1,0);
        fill(inidx,inidx+n+1,0);
        for(int i=0;i<n;i++) cin>>preorder[i];
        for(int i=0;i<n;i++) {cin>>inorder[i]; inidx[inorder[i]]=i;}
        postorder(0,n-1,0,n-1);
        cout<<'\n';
    }
    return 0;
}