문제
풀이
inorder, postorder가 주어졌을 때, preorder를 출력하는 문제이다. postorder의 끝 값이 항상 최상단 root가 되고 inorder에서는 그 root값 왼쪽은 왼쪽 자식, 오른쪽은 오른쪽 자식으로 만들 수 있다. 원리를 토대로 postorder에서 맨끝값을 찾아내고, inorder에서 그 root index를 기준으로 왼쪽자식이 몇개 있는지, 오른쪽 자식이 몇개 있는지를 찾아 postorder를 분할하고, 거기서 또 작은 postorder에서 root를 찾아내는 식을 반복한다. 이때마다 root를 출력하여 정답을 출력한다.
소스 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <iostream>
using namespace std;
int N;
int inorder[100001];
int postorder[100001];
int index_inorder[100001];
void preorder(int instart, int inend, int poststart, int postend){
if(instart > inend || poststart > postend) return;
int root = index_inorder[postorder[postend]];
printf("%d ", postorder[postend]);
preorder(instart, root-1, poststart, poststart + root - instart - 1);
preorder(root+1, inend, poststart + root - instart, postend-1);
}
int main(){
scanf("%d", &N);
for(int i = 1; i<=N; i++){
scanf("%d", &inorder[i]);
index_inorder[inorder[i]] = i;
}
for(int i = 1; i<=N; i++){
scanf("%d", &postorder[i]);
}
preorder(1, N, 1, N);
}
