문제
풀이
트리의 중위 순회, 후위 순회 정보를 통해 전위 순회를 찾아내는 문제이다. 분할 정복을 통해 풀어낼 수 있다.
다음의 트리를 예로 보자.
- 중위 순회 : 8 4 9 2 5 1 6 3 7
- 후위 순회 : 8 9 4 5 2 6 7 3 1
이제 tree의 중위 순회와 후위 순회 값들을 왼쪽 tree , 루트 노드 , 오른쪽 tree 로 분할해보자.
여기서 후위 순회의 끝 값은 항상 루트 노드 이기 때문에 중위 순회 값의 index들을 저장해주는 배열을 따로 만들어서 쉽게 중위 순회에서의 root 노드의 index 값을 찾아낼 수 있다.
1
2
3
4
5
for (int i = 1; i <= n; i++)
{
cin >> inorder[i];
Index[inorder[i]] = i; // inorder 요소들의 Index 정보 저장
}
1
int rootIndex = Index[postorder[postEnd]];
찾아낸 root 노드 값을 출력해주고 재귀 함수를 통해 더 이상 분해 할 수 없을 때 까지 tree를 위와 같이 분해해 가며 root 노드를 출력해준다. 다음은 재귀함수 코드이다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// preorder 를 출력하는 함수 (재귀)
void getPreOrder(int inStart, int inEnd, int postStart, int postEnd)
{
// 더 이상 분할 할 수 없는 경우 return
if (inStart > inEnd || postStart > postEnd)
return;
// postorder의 끝 값이 root값
// Index 배열을 통해 inorder에서의 root index를 쉽게 구할 수 있다.
int rootIndex = Index[postorder[postEnd]];
int leftSize = rootIndex - inStart;
int rightSize = inEnd - rootIndex;
cout << inorder[rootIndex] << ' '; // root 값 출력
// 재귀 함수 호출
getPreOrder(inStart, rootIndex - 1, postStart, postStart + leftSize - 1);
getPreOrder(rootIndex + 1, inEnd, postStart + leftSize, postEnd - 1);
}
분할 된 중위 순회의 시작 index, 끝 index 와
후위 순회의 시작 index, 끝 index 를 함수의 인자로 넣어주며 재귀 함수를 수행한다.
소스 코드
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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <iostream>
using namespace std;
int Index[100001];
int inorder[100001];
int postorder[100001];
int n;
// 입력 받기
void input()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> inorder[i];
Index[inorder[i]] = i; // inorder 요소들의 Index 정보 저장
}
for (int i = 1; i <= n; i++)
cin >> postorder[i];
}
// preorder 를 출력하는 함수 (재귀)
void getPreOrder(int inStart, int inEnd, int postStart, int postEnd)
{
// 더 이상 분할 할 수 없는 경우 return
if (inStart > inEnd || postStart > postEnd)
return;
// postorder의 끝 값이 root값
// Index 배열을 통해 inorder에서의 root index를 쉽게 구할 수 있다.
int rootIndex = Index[postorder[postEnd]];
int leftSize = rootIndex - inStart;
int rightSize = inEnd - rootIndex;
cout << inorder[rootIndex] << ' '; // root 값 출력
// 재귀 함수 호출
getPreOrder(inStart, rootIndex - 1, postStart, postStart + leftSize - 1);
getPreOrder(rootIndex + 1, inEnd, postStart + leftSize, postEnd - 1);
}
int main()
{
input();
getPreOrder(1, n, 1, n);
return 0;
}
