백준 2263(트리의 순회)

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

2263번: 트리의 순회

 

https://xkdlaldfjtnl.tistory.com/44

백준 4256(트리)

이 문제와 완벽하게 동일한 문제. 

 

단지 차이점은 문제의 예시가 좀 더 불 친절하다는 것이다. 

그래서 만약에 한번도 트리의 순회에 대해서 생각해보지 않았다면 접근하는데 더 어려울 문제

 

중위는 LVR

후위는 LRV 라는 것을 확인할 수 있다. 

 

두 순회를 갖고 나머지 하나의 순회과정이 어떠냐 묻는 문제에서 핵심은 

root를 찾는 것이라고 생각한다. 

 

root를 찾고 나면 중위에서 볼 수 있듯이 그 root의 왼쪽에는 L_subtree의 출력이, 오른쪽에는 R_subtree의 출력이 나온다. 

 

그렇다면 이 문제가 4256과 무슨 차이점이냐 하면 없다.

 

LRV의 출력을 거꾸로 하면 VRL순서대로 출력을 한 결과가 나온다. 따라서 동일하게 재귀함수를 통해서 r_subtree와 l_subtree로 나눈뒤 전위순회에 따라서 VLR순서대로 함수를 작성하면 된다. 

 

그리고 역시 index범위는 알아서 잘 설정해주자. 

 

#include<iostream>
using namespace std;
#define MAX 100001

int tmp1[MAX];
int tmp2[MAX];
int a[MAX];
int b[MAX];
int n;

void solve(int l, int r, int index) {
	if (l > r) return;
	int tmp = b[a[index]];

	cout << a[index] << " ";
	solve(l, tmp-1, index+1+r-tmp);
	solve(tmp+1, r, index+1);
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> tmp1[i];
	}
	for (int i = 0; i < n; i++) {
		cin >> tmp2[i];
	}
	for (int i = 0; i < n; i++) {
		a[i] = tmp2[n - 1 - i];
	}
	for (int i = 0; i < n; i++) {
		b[tmp1[i]] = i;
	}

	solve(0, n - 1, 0);

}