트리의 순회 (feat. 백준, 2263번)

트리의 순회
https://www.acmicpc.net/problem/2263

2263번: 트리의 순회

 

반응형

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
using namespace std;
int arr1[100001], arr2[100001];
int ans[100001];
void solution(register int is, register int ie, register int ps, register int pe) {
	if (is > ie || ps > pe)
		return;
	register int root = arr2[pe];
	cout << root << " ";
	solution(is, ans[root], ps, ps + (ans[root] - is) - 1);
	solution(ans[root] + 1, ie, ps + (ans[root] - is), pe - 1);
}
int main(void){
	ios::sync_with_stdio(false), cin.tie(NULL);
	register int N;
	cin >> N;
	for(register int i = 1; i <= N; ++i)
		cin >> arr1[i];
	for (register int i = 1; i <= N; ++i)
		cin >> arr2[i];
	for (register int i = 1; i <= N; ++i)
		ans[arr1[i]] = i;
	solution(1, N, 1, N);
	return 0;
}
// *&)*@*

트리 구조는 전위 순회, 중위 순회, 후위 순회 로 조회가 가능합니다.

이를 알고 있는지를 묻는 문제일뿐, 정답을 구하고자 투자하는 시간 대비 내용의 중요도는 낮습니다.