[BOJ/백준][Gold4] 4256 : 트리 (C++)

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

4256번: 트리

 

 

[난이도] Gold4
[유형] 분할정복

[풀이]
preorder 배열에서는 맨 앞의 원소가 root이다.
inorder 배열에서 root값을 찾으면 그 root값을 기준으로 좌측이 left child, 우측이 right child이다.
이 성질을 이용하여, 재귀함수로 left child, right child의 preoder,inorder 각각의 배열에서의 범위를 전달하는 방식으로 답을 구한다.

 

#include <cstdio>
int tc,N,pre[1001],in[1001];
void post(int lp,int rp,int li,int ri){
    if(lp>rp) return;
    if(lp==rp) {
        printf("%d ",pre[lp]);
        return;
    }
 
    int root = pre[lp];
    int idx=li;
 
    for(int i=li;i<=ri;i++){
        if(root==in[i]){
            idx=i;
            break;
        }
    }
    int lcnt = idx-li;
 
    post(lp+1,lp+lcnt,li,idx-1);
    post(lp+lcnt+1,rp,idx+1,ri);
    printf("%d ",pre[lp]);
}
int main(){
    scanf("%d",&tc);
    while(tc--){
        scanf("%d",&N);
        for(int i=0;i<N;i++) scanf("%d",&pre[i]);
        for(int i=0;i<N;i++) scanf("%d",&in[i]);
        post(0,N-1,0,N-1);
        puts("");
    }
}

 

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/4256.cpp