[백준] 2263 트리의 순회

문제

n개의 정점을 갖는 이진 트리의 정점에 1부터 n까지의 번호가 중복 없이 매겨져 있다. 이와 같은 이진 트리의 인오더와 포스트오더가 주어졌을 때, 프리오더를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다.

출력

첫째 줄에 프리오더를 출력한다.

 

 

 

풀이전략은 아래와 같습니다.

중위 순회   L M R 
1  2  3
trav(M)=trav(L) + M + trav(R)
>>루트가 2로 확정되면 
2 기준으로 좌 = trav(L)
2 기준으로 우 = trav(R)


후위 순회  L R M
1  3  2
후위순회의 마지막은 무조건 루트
>>루트가 2로 확정

trav(M)=trav(L)+trav(R)+M

중위 순회와 후위 순회가 주어진경우, 후위순위의 마지막 노드는 루트노드 M 입니다.

중위순회에서 노드 M을 기준으로 왼쪽은 왼쪽자식노드이고, 오른쪽은 오른쪽자식노드입니다.

 

따라서 divide and conquer 풀이전략으로

노드에서 conquer을 진행하고, 왼쪽 자식노드 , 오른쪽 자식노드로 divide하여 다시 conquer을 진행합니다.

만약 자식노드가 없거나 1개인경우 재귀를 마칩니다.

 

 

재귀를 진행할 때마다 왼쪽 오른쪽 각각의 트리를 만들면 비효율적이므로, 인덱스를 전달합니다.

#include<bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false),cin.tie(NULL);
#define mset(v) memset(v,0,sizeof(v));
#define rep(i,a) for(int i=0;i<a;++i)
#define REP(i,a) for(int i=1;i<=a;++i)

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef tuple<int, int, int>ti;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;

int n;
vi in, pre, post;
void recur(int infrom,int into,int postfrom,int postto) {
	int M = post[postto];
	cout << M << " ";
	if (infrom==into)return;

	int inmid = 0;
	for (int i = infrom; i <= into; i++) {
		if (in[i] == M) {
			inmid = i;
			break;
		}
	}
	int len = inmid - infrom;
	if(infrom<=inmid-1)
		recur(infrom,inmid-1,postfrom,postfrom+len-1);
	if(inmid+1<=into)
		recur(inmid+1,into,postfrom+len,postto-1);
}
int main() {
	FAST;
	cin >> n;
	int x;
	rep(i, n) {  //in
		cin >> x;
		in.push_back(x);
	}
	rep(i, n) { //post
		cin >> x;
		post.push_back(x);
	}
	recur(0,n-1,0,n-1);
}