PAT 1020

참고:
http://www.cnblogs.com/civi/archive/2013/03/03/2941805.html
아 날로 그 는 뒤의 순서 와 중간 순서 에 따라 여러 단계 로 옮 겨 다 니 며 코드 에 있 는 설명 을 참조 합 니 다.

#include <stdio.h>
#include <vector>
using namespace std;

vector<int> c[30];//c[i]   i   ，  30 

int a[30],b[30];//           

//a1,a2  a    ，b1,b2  b    
//  root,  b[root] == a[a2],      b    
//   root       len = root - b1
// root    a    （      ）：  a1 a1+len-1,      a1+len a2-1( a2  )
// root    b    （      ）：  b1 root-1,      root+1 b2
//  len == 0,     ， a1>a2，    
void traver(int d, int a1, int a2, int b1, int b2){
	int j;
	if(a1 == a2){
		c[d].push_back(a[a2]);
	}else if(a1 < a2){
		c[d].push_back(a[a2]);

		int tmp = a[a2];

		for(j=b1; j<=b2; j++){
			if(tmp == b[j]) break;
		}
		int root = j;
		int len = root - b1;
		traver(d+1, a1, a1+len-1, b1, root-1);
		traver(d+1, a1+len, a2-1, root+1, b2);
	}
}

int main(){
	//freopen("in.txt","r",stdin);
	int n;
	scanf("%d",&n);
	int i,j;

	for(i=0;i<n;i++){
		scanf("%d",&a[i]);
	}
	for(i=0;i<n;i++){
		scanf("%d",&b[i]);
	}	

	traver(0, 0, n-1, 0, n-1);

	int num = 0;
	i=0;

	while(1){
		int l = c[i].size();

		for(j=0; j<l; j++){
			printf("%d",c[i][j]);
			num ++;
			if(num < n) printf(" ");
		}
		if(num >= n) break;
		i++;
	}

	return 0;
}