백준 4256 트리

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

트리를 전위 탐색, 후위 탐색한 결과를 알려주고 트리의 후위 탐색 결과를 알아내는 문제이다.

전위,중위,후위 탐색이 궁금하다면 아래 글에서 코드를 보고 오자.

트리 탐색

2진트리의 경우 전위,중위 결과를 알거나 중위,후위 결과를 알면 트리의 모양을 하나로 단정지을수 있다. 문제의 상황처럼 전위, 중위 결과를 안다고 가정하자.

전위 탐색: root, left sub-tree, right sub-tree 후위 탐색: left sub-tree, root, right sub-tree

따라서 우리는 전위 탐색에서 root를 구할 수 있고, 후위 탐색에서 root를 기준으로 left sub-tree 와 right sub-tree의 구간을 구할 수 있다.

단, 전위 탐색에서의 sub-tree와 중위 탐색에서의 sub-tree는 같은 sub-tree여도 탐색이 다르므로 순서가 다를 수 있다.

#include<bits/stdc++.h>
using namespace std;
const int SZ=1005;
int pre[SZ];
int in[SZ];
void tra(int p1, int p2, int q1, int q2){
	if(p1>p2) return;
	int left_num=0;
	for(int i=q1;i<=q2;i++){
		if(in[i]==pre[p1]) break;
		left_num++;
	}
	tra(p1+1,p1+left_num,q1,q1+left_num-1);
	tra(p1+left_num+1,p2,q1+left_num+1,q2);
	cout<<pre[p1]<<" ";
}
int main(void){
	ios::sync_with_stdio(false); cin.tie(NULL);
	int t; cin>>t;
	while(t--){
		int n; cin>>n;
		for(int i=1;i<=n;i++) cin>>pre[i];
		for(int i=1;i<=n;i++) cin>>in[i];
		tra(1,n,1,n);
		cout<<'\n';
	}
	return 0;
}