백준 4256: 트리

문제 요약

BT(Binary Tree)를 전위 순회, 중위 순회한 결과가 주어진다. 즉, 위의 함수 중 preorder(root node of BT)와 inorder(root node of BT)를 호출해서 만든 리스트가 주어진다. 두 순회한 결과를 가지고 다시 BT를 만들 수 있다. BT의 전위, 중위 순회한 결과가 주어졌을 때, 후위 순회했을 때의 결과를 구하는 프로그램을 작성하시오.

문제 분류

• 트리
• 분할 정복
• 재귀

문제 풀이

전위 순회와 중위 순회의 특징을 파악하는 문제이다. 전위 순회에서 맨 왼쪽부터 차례대로 노드를 선택하여, 선택한 노드를 중위 순회에서 찾으면, 찾은 노드는 로트 노드가 되어 왼쪽 부분은 왼쪽 서브트리, 오른쪽 부분은 오른쪽 서브트리가 된다.

후위 순회는 루트 노드의 왼쪽 서브트리를 모두 출력하고 오른족 서브트리를 모두 출력한 다음 자신(루트 노드를)출력하면 되므로 이를 재귀로 구현하면 된다.

즉, 자신을 기준으로 왼쪽과 오른쪽을 모두 출력하는 느낌의 분할 정복 문제라 보아도 무방하다.

전위 순회는 그대로 입력 받았지만, 중위 순회에서는 순서가 중요하므로 각 노드 번호에 순서를 대입하여 사용하였다. 즉, 어떠한 배열 i번째에 노드 k의 값을 넣는 게 아닌, 어떠한 배열의 k인덱스에 i를 넣었다.

문제가 이진 트리인 점에서 두 부분밖에 신경쓰지 않아도 된다는 점을 착안했다.

메모리 초과를 일으켜 int가 아닌 short를 사용하게 되어서 scanf(), printf()또한 %d에서 %hd로 고쳐야 한다.

풀이 코드

#include <stdio.h>
#include <iostream>

using namespace std;

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

void postOrder(int idx, int L, int R) {
	if (idx >= n) return;
	if (L >= R) return;
	bool l = false, r = false;
	for (int i = 0; i < n; i++) {
		if (in[pre[i]] >= L && in[pre[i]] < in[pre[idx]] && !l) {
			l = true;
			postOrder(i, L, in[pre[idx]]);
		}
		else if (in[pre[i]] > in[pre[idx]] && in[pre[i]] < R && !r) {
			r = true;
			postOrder(i, in[pre[idx]] + 1, R);
		}
	}
	printf("%d ", pre[idx]);
}
int main() {
	int t, in1;
	cin >> t;
	while (t--) {
		scanf("%d", &n);
		for (int i = 0; i < n; i++)
			scanf("%d", pre + i);
		for (int i = 0; i < n; i++) {
			scanf("%d", &in1);
			in[in1] = i + 1;
		}
		postOrder(0, 1, n + 1);
		printf("\n");
	}
	return 0;
}