백준 2263 트리의 순회

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

2263번: 트리의 순회

 

In-Order와 Post-Order를 보고 Pre-Order를 유추하는 문제다.

 

Post-Order의 제일 마지막 Node가 그 Tree의 Root Node가 된다. 

 

해당 문제는 다음과 같은 예시를 제공한다.

 

In Order : 1 2 3

Post Order : 1 3 2

 

Post Order의 제일 마지막에 있는 2가 root 노드이다.

그러면 In order에서 2를 찾는다( 각 노드번호는 고유하다) 

 

In Order에서 2를 중심으로 두 트리는 나뉘게 된다. 즉 2가 분절점이다.

 

풀이는 이를 반복한다.

 

Post Order에서 제일 마지막 노드를 In Order에서 찾는다. 

그 찾은 노드를 기준으로 In Order를 절반으로 나눈다.

Post Order와 나뉜 in Order를 Matching 시킨다. 

다시 나뉜 각각의 Post Order의 제일 마지막 노드가 해당 Sub tree의 Root node이다. 

 

어렵다... 코드를 보자

 

/* 트리의 순회 */

#include <iostream>
#include <vector>

using namespace std;

void recur(int, int, int, int);
void input();
void solve();

int N;
vector<int> pre_order, post_order, in_order;

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	
	input();
	solve();	

	return 0;
}

// Postorder에서 r-1을 Inorder에서 찾아서 그 r-1을 찾아서 
// 그 찾은 target의 바로 왼쪽을 다시 r로 보낸다. 
void recur(int in_order_start, int in_order_end, int post_order_start, int post_order_end) {

	if (in_order_start > in_order_end || post_order_start > post_order_end) return;

	int target = post_order[post_order_end];

	cout << target << " ";

	for (int i = in_order_start; i <= in_order_end; i++) {
		if (in_order[i] == target) {
			recur(in_order_start, i - 1, post_order_start, post_order_start + i - in_order_start - 1 );
			recur(i + 1, in_order_end, post_order_start + i - in_order_start, post_order_end-1);
		}
	}
}

void input() {
	cin >> N;
	in_order.resize(N); post_order.resize(N);

	for (int i = 0; i < N; i++) cin >> in_order[i];
	for (int i = 0; i < N; i++) cin >> post_order[i];
}

void solve() {
	recur(0, N - 1, 0, N-1);
}