[한 마리의 갈매기 출제 과정] [PAT] A1020 나무가 두루 다니고 있습니다.

Suppose that all the keys in a binary tree are distinct positive integers. Given the postorder and inorder traversal sequences, you are supposed to output the level order traversal sequence of the corresponding binary tree.

Input Specification:

Each input file contains one test case. For each case, the first line gives a positive integer N (≤30), the total number of nodes in the binary tree. The second line gives the postorder sequence and the third line gives the inorder sequence. All the numbers in a line are separated by a space.

Output Specification:

For each test case, print in one line the level order traversal sequence of the corresponding binary tree. All the numbers in a line must be separated by exactly one space, and there must be no extra space at the end of the line.

Sample Input:

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

Sample Output:

4 1 6 3 5 7 2

제목 대의:

두 갈래 나무의 모든 키가 서로 다른 정수라고 가정해 보세요.정렬 후 순환 시퀀스와 질서 순환 시퀀스를 지정합니다. 해당 두 갈래 트리의 층계 순환 시퀀스를 출력해야 합니다.

입력 사양:

입력 파일마다 테스트 용례가 포함되어 있습니다.각 상황에 대해 첫 번째 줄은 정수 N(≤30), 즉 두 갈래 나무의 노드 총수를 제시한다.두 번째 줄은 뒷순서를 제시했고, 세 번째 줄은 순서를 제시했다.한 줄의 모든 숫자는 공백으로 구분된다.

출력 사양:

모든 테스트 용례에 대해 한 줄에 해당하는 두 갈래 나무의 등급 순서를 인쇄합니다.한 줄의 모든 숫자는 공백으로 완전히 구분되어야 하며, 줄 끝에 공백이 남아서는 안 된다.

샘플 입력:

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

샘플 출력:

4 1 6 3 5 7 2

코드:

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
struct node{
	int data;
	node *left,*right;
};
int in[40],post[40];// ， 

node *build(int hz,int hy,int zz,int zy) 
// （ ， ， ， ）
{
	if(hz>hy)  // 0
	return NULL;
	node *root = new node;
	root->data = post[hy]; // 
	int k;
	for(k=zz;k<=zy;k++) // 
	{
		if(in[k] == post[hy])
		break;
	}
	int numleft = k-zz;  // 
	root->left = build(hz,hz+numleft-1,zz,k-1);
	root->right = build(hz+numleft,hy-1,k+1,zy);
	return root;
}

void lay(node *root) // 
{
    queue<node*> q;
	q.push(root);
	vector<int> v;  // ， vector 
	while(q.size())
	{
		node *now = q.front();
		v.push_back(now->data);
		q.pop();
		if(now->left!=NULL) q.push(now->left);
		if(now->right!=NULL) q.push(now->right);
 	}	
 	for(int i=0;i<v.size();i++) // 
 	{
 		cout<<v[i];
 		if(i<v.size()-1)
 		cout<<" ";
	 }

}
int main() 
{
   int n;
   cin>>n;
   for(int i=0;i<n;i++) // 
     cin>>post[i];
   for(int i=0;i<n;i++) // 
     cin>>in[i];
     
    node *root = build(0,n-1,0,n-1); // ， root 
    lay(root); // 
    return 0;
}