[백준][C++] 4256번: 트리

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

4256번: 트리

 

이진 트리를 전위, 중위 순회한 결과가 주어졌을 때 후위 순회한 결과를 출력하는 문제이다.

 

먼저 전위 순회는 루트 노드 -> 왼쪽 자식 -> 오른쪽 자식 순으로 방문하고 

중위 순회는 왼쪽 자식 -> 루트 노드 -> 오른쪽 자식 순으로 방문한다.

 

예제 입력으로 주어진

전위 순회한 결과 : 3 6 5 4 8 7 1 2와 

중위 순회한 결과 : 5 6 8 4 3 1 2 7를 보자.

 

일단 전위 순회한 결과를 통해 3이 전체 트리의 루트 노드라는 것은 바로 알 수 있다.

그러면 알아낸 루트 노드를 가지고 중위 순회한 결과를 보면 루트 노드를 기준으로

5 6 8 4 3 1 2 7 에서 5 6 8 4 는 왼쪽 서브 트리, 1 2 7 은 오른쪽 서브 트리가 되는 것을 알 수 있다.

 

그 다음 전위 순회한 결과에서의 6은 왼쪽 서브 트리의 루트 노드라는 것을 알 수 있다.이를 통해 왼쪽 서브 트리를 나눠보면 5 6 8 4 로 왼쪽 서브 트리 5, 오른쪽 서브 트리 8 4 가 된다.

 

이처럼 전위 순회한 결과로는 각 트리의 루트 노드를 구할 수 있고 중위 순회한 결과로는 구한 루트 노드를 통해 왼쪽, 오른쪽 서브 트리로 나눌 수가 있다.

 

이제 알아낸 로직으로 후위 순회한 결과를 출력해야 하는데후위 순회는 왼쪽 자식 -> 오른쪽 자식 -> 루트 노드 순이다. 뭔가 재귀 함수로 지지고 볶으면 될 것 같다는 느낌을 받았다.위에서 중위 순회한 결과에서 왼쪽, 루트, 오른쪽으로 나눌 수 있었는데 이걸 왼쪽, 오른쪽, 루트 순으로 출력해주면 후위 순회한 결과가 된다.그러면 재귀 함수로 중위 순회에서 나눈 왼쪽 서브 트리를 후위 순회한 결과를 출력하고 그 다음 오른쪽 서브 트리를 후위 순회, 마지막으로 루트 노드를 출력해주는 식으로 풀어보았다.

 

#include <iostream>

using namespace std;

int pre[1001];
int in[1001];
int n;

void postOrder(int start, int end, int root_idx) {
	for(int i=start; i<end; i++) {
		if(pre[root_idx] == in[i]) {
			postOrder(start, i, root_idx+1); // 왼쪽
			postOrder(i+1, end, root_idx+1+i-start); // 오른쪽
			cout << pre[root_idx] << " "; 
		}
	}
}

void solve() {
	int root_idx = 0;
	postOrder(0, n, root_idx);
	cout << "\n";
}

int main(void) {
	int T;
	cin >> T;
	while(T--) {
		cin >> n;
		
		for(int i=0; i<n; i++) {
			cin >> pre[i];
		}
		for(int j=0; j<n; j++) {
			cin >> in[j];
		}
		solve();
	}
}

 

 

로직을 생각해내는 것이 쉽지 않았고 생각해낸 로직을 구현하는 것은 더 쉽지 않았다.

직관적으로 떠오르지 않으면 풀 수 없을 것 같다. 재귀 문제를 공식처럼 풀 수 있을까?

실력이 부족해서인지 아직까지는 알고리즘은 IQ싸움같다 ㅋㅋ