[BOJ] 2263번 트리의 순회 (C++)

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

2263번: 트리의 순회

 

#include <iostream>
using namespace std;

int Index[100001];
int inOrder[100001];
int postOrder[100001];

void getPreOrder(int inStart, int inEnd, int postStart, int postEnd){
	if(inStart > inEnd || postStart > postEnd) return;
	
	int rootIndex = Index[postOrder[postEnd]];
	int leftSize = rootIndex - inStart;
	int rightSize = inEnd - rootIndex;
	
	cout << inOrder[rootIndex] << ' ';
	getPreOrder(inStart, rootIndex - 1, postStart, postStart + leftSize - 1);
	getPreOrder(rootIndex + 1, inEnd, postStart + leftSize, postEnd - 1);
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	int n;
	cin >> n;
	for(int i = 1; i <= n; i++) {
		cin >> inOrder[i];
		Index[inOrder[i]] = i;
	}
	for(int i = 1; i <= n; i++) 
		cin >> postOrder[i];
	
	getPreOrder(1, n, 1, n);
	return 0;
}

 

위의 예시처럼 중위 순회와 후위 순회 값들을 왼쪽 tree, 루트 노드, 오른쪽 tree로 분할할 수 있다.

후위 순회의 끝은 항상 루트 노드이기 때문에 중위 순회 값의 index를 저장하는 배열을 따로 만들어서 중위 순회에서의 root 노드의 index 값을 찾아낼 수 있다.

root 노드의 index 값을 활용해 root 노드 값을 출력하고 재귀 함수를 통해 더 이상 분해할 수 없을 때까지 왼쪽 tree와 오른쪽 tree로 분해해가며 root 노드를 출력해준다.