엘리베이터 L2-011 두 갈래 나무 타기(25분)

두 갈래 나무의 중차순과 전차순을 정해 주십시오. 먼저 나무를 거울로 반전시킨 다음에 반전된 층차순의 서열을 출력해 주십시오.거울 반전이란 모든 비엽결점의 좌우 아이를 맞바꾸는 것을 말한다.여기서 키 값이 서로 같지 않은 정수라고 가정합니다.

형식 입력:

첫 번째 줄을 입력하면 정수N(≤30)가 두 갈래 나무의 결점 개수입니다.두 번째 줄은 그 중의 서열을 반복한다.세 번째 줄은 앞의 순서를 반복해서 보여 준다.숫자 사이는 공백으로 구분된다.

출력 형식:

한 줄에서 이 트리가 반전된 후 겹쳐진 시퀀스를 출력합니다.숫자 사이는 1개의 공백으로 구분되며, 줄의 앞뒤에 여분의 공백이 있어서는 안 된다.

샘플 입력:

7
1 2 3 4 5 6 7
4 1 3 2 6 5 7

내보내기 예제:

4 6 1 7 5 3 2

프로그램:

#include 
#include 
#include 
#include 
using namespace std;
struct node
{
	int data;
	struct node *left,*right;
};
struct node* build(vector pre,vector in,int a,int b,int c,int d)
{
	if(a > b) return NULL;
	struct node* root = (struct node*)malloc(sizeof(struct node));
	root->data = pre[a];
	int pos = c;
	while(in[pos] != pre[a])
	{
		pos++;
	}
	root->left = build(pre,in,a+1,a+pos-c,c,pos-1);
	root->right = build(pre,in,a+pos-c+1,b,pos+1,d);
	return root;
}
void Reverse(struct node* &root)
{
	if(root)
	{
		Reverse(root->left);
		Reverse(root->right);
		struct node* temp = root->left;
		root->left = root->right;
		root->right = temp;
	}
}
void levelOrder(struct node* root)
{
	queue q;
	q.push(root);
	vector v;
	while(!q.empty())
	{
		struct node* temp = q.front();
		v.push_back(temp->data);
		q.pop();
		if(temp->left)
			q.push(temp->left);
		if(temp->right)
			q.push(temp->right);
	}
	for(int i = 0; i < v.size(); i++)
	{
		if(i == 0)
			printf("%d",v[i]);
		else
			printf(" %d",v[i]);
	}
	printf("
");
}
int main()
{
	int n;
	scanf("%d",&n);
	vector pre(n),in(n);
	for(int i = 0; i < n; i++)
	{
		scanf("%d",&in[i]);
	}
	for(int i = 0; i < n; i++)
	{
		scanf("%d",&pre[i]);
	}
	struct node* root = build(pre,in,0,n-1,0,n-1);
	Reverse(root);
	levelOrder(root);
	return 0;
}