백준 2263 트리의 순회

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

2263번: 트리의 순회

이문제는 트리 순회의 특징을 이용하여 문제를 해결해야한다. 사용할 트리의 특징들이 무엇 이냐면

 

1. 후위순회(postorder)의 가장 마지막 노드는 루트 노드이다.

후위순회를 돌때 가장 마지막 노드는 트리의 루트노드이다. 

 

2. 중위순회(inorder)

중위순회에서는 루트의 왼쪽 노드들은 루트의 왼쪽에 위치한 노드들이고 오른쪽 노드들은 오른쪽에 위치한 노드들이다. 

 

그림을 보면 루트 노드를 구분한 후 왼쪽과 오른쪽 도 처음과 똑같은 연산을 진행해주는 것을 확인할 수 있다. 이말은 즉 분할 정복을 사용하여 풀어야 한다는 의미이다. 

 

후위 순회의 루트의 정보를 이용하여 중위 순회의 root를 찾은 다음 좌우 구분하여 다시 반복해주면 문제를 해결 할 수 있다. 처음에는 노드를 구분하는데 이분탐색을 사용했는데 시간초과가 발생했다. ㅠㅠ 

 

중위 순회의 값을 넣을 때 각 노드가 몇번째로 출몰했는지 값을 넣어 주었다. 아래의 코드를 보면 더 이해할 수 있을 것이다. 

 

백준의 입력이 너무 간단해서 내가 추가로 만든 예시를 올려놓는다.

15
8 4 9 2 10 5 11 1 12 6 13 3 14 7 15
8 9 4 10 11 5 2 12 13 6 14 15 7 3 1

output
1 2 4 8 9 5 10 11 3 6 12 13 7 14 15

 

 

#include <cstdio>

int n;
int postOrder[100002];
int inOrder[100002];
int appearence[100002];

void push();
void getPreorder(int inStart, int inEnd, int postStart, int postEnd);

int main(){
	push();
	getPreorder(1, n, 1, n);
}


void push(){
	scanf("%d", &n);
	for(int i = 1; i <= n; i++){
		scanf("%d", &inOrder[i]);
		appearence[inOrder[i]] = i;
	}
	for(int i = 1; i <= n; i++)
		scanf("%d", &postOrder[i]);
}

void getPreorder(int inStart, int inEnd, int postStart, int postEnd){
	if(inStart > inEnd || postStart > postEnd)
		return;
	int rootIndex = appearence[postOrder[postEnd]];
	int leftSize = rootIndex - inStart;
	int rightSize = inEnd - rootIndex;
	printf("%d ", postOrder[postEnd]);
	getPreorder(inStart, rootIndex-1, postStart, postStart+leftSize-1);
	getPreorder(rootIndex+1, inEnd, postStart+leftSize, postEnd-1);
}