[백준 BOJ][C++]2263번 트리의 순회: 분할 정복

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

2263번: 트리의 순회

 

 

이 문제는 재귀 함수를 통한 분할 정복을 이용하여 해결할 수 있습니다. 

 

인오더는 왼쪽 자식 → 부모 → 오른쪽 자식

포스터오더는 왼쪽 자식 → 오른쪽 자식 → 부모

프리오더는 부모 → 왼쪽 자식 → 오른쪽 자식

 

예를 들어 다음과 같은 트리의 인오더와 포스터오더가 주어진다고 가정하겠습니다. 

index	0	1	2	3	4	5	6	7	8
인오더	4	8	2	5	1	9	6	3	7
포스터	8	4	5	2	9	6	7	3	1

 

 이때 포스터 오더의 마지막 순서는 항상 루트 노드이기 때문에, 1이 루트 노드인 것을 확인할 수 있습니다. 

 

 인오더는 왼쪽 자식, 부모, 오른쪽 자신 순이기 때문에 부모 노드를 기준으로 왼쪽 서브 트리, 오른쪽 서브 트리로 나눌 수 있습니다. 

 

 포스터오더는 왼쪽 자식, 오른쪽 자식, 부모 순이기 때문에 인오더의 오른쪽 서브 트리의 노드 개수만큼 앞으로 당긴다면, 왼쪽 서브트리의 부모 노드를 알 수 있겠죠?

 

index	0	1	2	3	4	5	6	7	8
인오더	4	8	2	5	1	9	6	3	7
포스터	8	4	5	2	9	6	7	3	1

 

 1을 기준으로 인오더에서 오른쪽 서브 트리의 노드 개수는 4개이므로 포스터오더에서 4개만큼 앞으로 당겨오면 왼쪽 서브트리의 최상단 부모노드를 알 수 있습니다! 이때 이 노드는 2가 됩니다. 

 

index	0	1	2	3	4	5	6	7	8
인오더	4	8	2	5	1	9	6	3	7
포스터	8	4	5	2	9	6	7	3	1

 

 이때 다시 2를 기준으로 오른쪽 서브 트리의 노드 개수는 1개 이므로 포스텉오더에서 1개만큼 앞으로 당겨오면 다음 최상단 부모노드를 알 수 있습니다. 

 

 이제 루트 노드 1을 기준으로 왼쪽 서브트리의 모든 부모 노드(1, 2, 4)는 다 찾은 것 같죠?

 

 2와 4의 오른쪽 자식 노드인 5와 8은 리프 노드이므로 단순히 추가합니다. 

 

 이때까지의 순서는 1, 2, 4, 8, 5가 됩니다.

 

 이제 1을 기준으로 오른쪽 서브 트리로 뻗어나가봅시다!

 

index	0	1	2	3	4	5	6	7	8
인오더	4	8	2	5	1	9	6	3	7
포스터	8	4	5	2	9	6	7	3	1

 

오른쪽 서브트리의 최상단 부모 노드는 포스터 오더에서 루트 노드인 1 이전의 노드이겠죠? 

 

 3을 기준으로 오른쪽 서브트리의 노드 개수는 1개이므로 그 다음 부모 노드는 6이 됩니다. 

 

 이 과정을 계속해서 반복하면 됩니다!

 

 

 

< solution(int pIdx, int s, int e) >

- parameters

• int pIdx: 포스터 오더 배열의 원소를 접근할 인덱스, post[pIdx]가 차례대로 ans 배열에 추가됨
• int s: 인오더 배열의 원소를 탐색할 시작 인덱스
• int e: 인오더 배열의 원소를 탐색할 마지막 인덱스

 

- variables

• left: 인오더 배열에서 post[pIdx] 기준으로 왼쪽 서브 트리 개수
• right: 인오더 배열에서 post[pIdx] 기준으로 오른쪽 서브 트리 개수
• i: 인오더 배열에서 post[pIdx]와 같은 값을 갖는 원소의 인덱스

#include<iostream>
#include<vector>

using namespace std;

int n;
int root;
vector<int> in;
vector<int> post;
int ans[100001] = { 0, };
int idx = 0;

void solution(int pIdx, int s, int e) {
	int left, right;
	int i;
	ans[idx++] = post[pIdx];

	if (s >= e)
		return;

	for (i = s; i <= e; i++) {
		if (in[i] == post[pIdx]) {
			left = i - s;
			right = e - i;
			break;
		}
	}

	if (left > 0) {
		solution(pIdx - right - 1, s, i - 1);
	}
	if (right > 0) {
		solution(pIdx - 1, i + 1, e);
	}
	
}

int main(void) {

	cin >> n;

	for (int i = 1; i <= n; i++) {
		int x;
		cin >> x;
		in.push_back(x);
	}
	for (int i = 1; i <= n; i++) {
		int x;
		cin >> x;
		post.push_back(x);

		if (i == n) {
			root = x;
		}
	}

	solution(n - 1, 0, n - 1);

	for (int i = 0; i < n; i++) {
		cout << ans[i] << " ";
	}

	return 0;
}