[2263] 트리의 순회

---

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

2263번: 트리의 순회

분할정복 문제이다.

 

일단 트리의 순회 3 종류를 알아야 한다.

중위 순회는 left -> root -> right

후위 순회는 left -> right -> root

전위 순회는 root -> left -> rigjt

순서이다.

 

우리가 받는 정보는 중위 순회와 후위 순회이다.

root를 기준으로 left/right를 나누어서 계속 탐색하면 된다.

 

하지만 중위 순회 정보만으로는 어느 것이 root 노드인지 알 수 없다.

그러므로 후위 순회의 정보를 이용한다.

후위 순회는 항상 맨 마지막 노드가 root 노드이기 때문이다!

 

그럼 정보를 이용하여 어떻게 탐색하느냐?

후위 순회는 root -> left -> right 순서인데, 이를 이용할 것이다.

1. root 노드 찾고 출력

2. left 탐색

3. right 탐색

위의 그림으로 예시를 들어보았다.

빨간색이 root = inorder[rootIndex] = postorder[post_max]를 뜻한다.

따라서 위의 예시에서 전위 순회는 1 - 2 - 4 - 8 - 5 - 3 - 6 - 7이다.

 

다음 탐색 index의 범위를 구하는게 살짝 이해가 안되지만.. 시간을 두고 천천히 이해해보려고 한다.

#include <iostream>
using namespace std;

int N;
int inorder[100000];
int postorder[100000];
int position[100001];

void preorder(int in_min, int in_max, int post_min, int post_max) {
	if (in_min > in_max || post_min > post_max) {
		return;
	}

	int root = postorder[post_max]; // 후위 순회로 root를 구함
	int rootIndex = position[root]; // 중위 순회 기준으로 하는 root의 index를 구함

	printf("%d ", root);

	// left
	preorder(in_min, rootIndex - 1,
		post_min, post_min + (rootIndex - 1) - in_min);
	// right
	preorder(rootIndex + 1, in_max, 
		(post_min + rootIndex) - in_min, post_max - 1);

}

int main() {
	cin >> N;

	// 중위 순회
	for (int i = 0; i < N; i++) {
		cin >> inorder[i];
		position[inorder[i]] = i;
		// position[x] = y : x의 인덱스는 y이다.
		// inorder 값들의 위치 정보를 저장하고 싶어	
	}

	// 후위 순회 : 맨 마지막 노드가 root 노드
	for (int i = 0; i < N; i++) {
		cin >> postorder[i];
	}

	preorder(0, N - 1, 0, N - 1);
}