[ boj : 2263 ] 트리의 순회

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

2263번: 트리의 순회

문제 : inorder와 postorder가 주어질때 preorder를 출력해라

해설 : 크게 왼쪽 트리와 오른쪽 트리로 나누어야 되는데 매번 나눌때마다 postorder에 가장 오른쪽 값이 서브트리의 부모노드가 됩니다. 이 말은 즉슨 매번 postorder의 가장 오른쪽 값을 출력하면 그게 바로 preorder 순서대로 출력한 값이 됩니다.

inorder를 탐색할 l과r을 선언해주고, postorder를 탐색할 l과 r을 따로 선언해줍니다.

이후에 왼쪽트리부터 탐색하고 그 후 오른쪽 트리로 탐색해 줍시다.

#include<bits/stdc++.h>

using namespace std;

int in[100010], post[100010],arr[100010];
void f(int il, int ir, int pl, int pr);

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

	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> in[i];
		arr[in[i]] = i;
	}
	for (int i = 0; i < n; i++)cin >> post[i];

	f(0, n - 1, 0, n - 1);
}
void f(int il, int ir, int pl, int pr)
{
	if (il > ir || pl > pr)return;

	int ans = post[pr];
	cout << ans << " ";

	f(il, arr[ans] - 1, pl, pr - (ir - arr[ans] + 1));
	f(arr[ans] + 1, ir, pl + (arr[ans] - il), pr - 1);
}