백준 2263 트리의 순회

 

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

문제와 채점은 위 사이트에서 확인 하실 수 있습니다.

 

이 문제는 트리의 중위 순회 순서와 후위 순회 순서를 입력받아 전위 순회 순서를 출력하는 문제입니다.

중위 순회와 후위 순회를 예를 만들어서 보게되면 후위 순회의 가장 끝이 항상 root를 나타냄을 알 수 있고

중위 순회에서는 그 루트를 기준으로 왼쪽에 있는 값들이 왼쪽 자식들이고 오른쪽에 있는 값들이 오른쪽 자식임을

알 수 있습니다. 따라서 이 특성을 이용하여 분할 정복을 통해 문제를 풀어야 합니다. 헷갈려서 쉽지 않은 문제였습니다,,

 

다음은 코드입니다.

 

 

#include <iostream>

using namespace std;

int in[200000];
int post[200000];
int n;

void preorder(int istart, int iend, int pstart, int pend) {
	
	if(istart > iend || pstart > pend)
		return;
	
	int root = post[pend];
	cout<<root<<' ';
	int left = in[root] - istart; 
	 
	preorder(istart, in[root]-1, pstart, pstart + left - 1);
	preorder(in[root]+1, iend, pstart + left, pend - 1);
	return; 
} 

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> n;
	for(int i = 1; i <= n; i++) {
		int x; cin >> x;
		in[x] = i;
		}
	for(int i = 1; i <= n; i++)
		cin >> post[i];
	
	preorder(1, n, 1, n); // 위치확인 왼쪽 오른쪽 탐색해서 트리 모양 유추 가능 
	
	return 0;
}