트리
문제 해석
전위순회,중위순회한 결과가 주어졌을 때, 후위순회 결과를 출력하는 문제입니다.
설계(10)
전위순회는 루트->왼쪽서브트리->오른쪽서브트리 순으로 순회하기 때문에, 맨처음 인덱스가 최상위 루트인 것을 쉽게 알 수 있습니다.
또한, 중위순회는 왼쪽서브트리->루트->오른쪽서브트리 순으로, 루트를 기준으로 왼쪽,오른쪽 서브트리가 나뉜다는 것을 알 수 있습니다.
이를 이용하여 최상위루트(인덱스 0)부터 시작하여 각 하위 루트를 찾으면 됩니다.
구현(20)
코드
#include <iostream>
using namespace std;
#define MAXN 1000
int in[MAXN],pre[MAXN];
int N;
void post(int start, int end, int root){
for (int i = start; i<=end;i++){
if (in[i]==pre[root]){
post(start,i-1,root+1);
post(i+1,end,root+i-start+1);
printf("%d ",in[i]);
}
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int t;
cin >> t;
while (t--){
cin >> N;
for (int i = 0 ; i <N; i++){
cin >> pre[i];
}
for (int i = 0 ; i <N; i++){
cin >> in[i];
}
post(0,N-1,0);
printf("\n");
}
return 0;
}
디버깅
제출결과
36 ms
마무리
트리의 특성을 이해하면 구현이 가능한 문제였습니다.
각 순회가 어떻게 이루어져있는지 배울 수 있는 좋은 문제인 것 같습니다.