Original title: https://pintia.cn/problemsets/994805342720868352/problems/994805519074574336

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:

Sample Output:

Topic analysis:
The binary tree is constructed by postorder and inorder of binary tree and traversed hierarchically.
That is, the latter order (left and right roots) finds the root node, and the middle order (left and right roots) divides the left and right subtrees.

Style 1
Step by step according to the establishment of binary tree and hierarchical traversal, the establishment of binary tree recursion, hierarchical traversal stack:

/* 1020 Tree Traversals (25 Points) */
#include<iostream>
#include<queue>

using namespace std;

int PostOrder[30]; // Post order
int Inorder[30]; // Middle order
int Len;         // Number of nodes in the input tree
int flag = 1;    // Is it the first output?

typedef struct node {
	int data;
	struct node* left;
	struct node* right;
}BNode,*BTree;

// Solution, after order (left and right root) to find the root, in order (left and right root) to recurse
int FindElem(int* arr, int e, int len) {
	// Find the index of e in array arr
	int i;
	for (i = 0; i < len && arr[i] != e; i++);
	if (i == len) return -1;
	else return i;
}
int FindRoot(int start, int end) {
	// Find the root from Inorder[start,...,end] and return the subscript
	// Compare who has the lowest index in PostOrder
	int root = Inorder[start];
	int root_index = start;
	int index = FindElem(PostOrder, root,Len);
	for (int i = start + 1; i <= end; i++) {
		int index_ = FindElem(PostOrder, Inorder[i], Len);
		if (index_ > index) {
			root = Inorder[i];
			root_index = i;
			index = index_;
		}
	}
	return root_index;
}
void CreateTree(int start, int end, BTree& T) {
	// T represents root
	if (end < start || start > end) {
		T = NULL;  // Note that T changes here, so you need to pass it by reference.
		return;
	}
	int root = FindRoot(start, end);
	T->left = (BNode*)malloc(sizeof(BNode));
	T->right = (BNode*)malloc(sizeof(BNode));
	T->data = Inorder[root];
	CreateTree(start, root - 1, T->left);
	CreateTree(root + 1, end, T->right);
}

void LevelTravel(BTree T) {
	// Hierarchical traversal of tree T
	queue<BTree> Q; // Traversing node queues
	Q.push(T);
	while (!Q.empty()) {
		BTree e;
		e = Q.front(); Q.pop();
		if (flag == 0) {
			printf(" ");
		}
		printf("%d", e->data);
		flag = 0;
		if (e->left) Q.push(e->left);
		if (e->right) Q.push(e->right);
	}
}
int main() {
	scanf("%d", &Len);
	int i;
	for (i = 0; i < Len; i++) scanf("%d", &PostOrder[i]);
	for (i = 0; i < Len; i++) scanf("%d", &Inorder[i]);
	BTree T;
	T = (BNode*)malloc(sizeof(BNode));
	T->left = T->right = NULL;
	CreateTree(0, Len - 1, T);
	LevelTravel(T);
	system("pause");
	return 0;
}

Style II (Simplification)
The binary tree is also established by root traversal, but the index is used to simplify the establishment of order traversal by post-order traversal and middle-order traversal.
Assume that the node array starts at start and ends at end.
Since the last node of the post-order traversal is always the root node of the tree, and its index in Post is rootroot root, it is assumed that in the middle-order traversal the node is subscribed I I i, then the right subtree has (end_i+1)(end-i+1)(end_i+1) nodes. So in the latter order, the root node is rootroot root, the root node of the right subtree is root_1root-1 root_1, and the root node of the left subtree is root_ (end_i+1)=(root_end+i_1) root - (end-i+1)=(root-end+i-1) root_ (end_i+1)=(root_i+1) = (root_end+i_1).
Then there are

/* 1020 Tree Traversals (25 Points) */
#include<iostream>
#include<queue>

using namespace std;

int Postorder[30]; // Post order
int Inorder[30]; // Middle order
int Len;         // Number of nodes in the input tree
int flag = 1;    // Is it the first output?

typedef struct node {
	int data;
	struct node* left;
	struct node* right;
}BNode, *BTree;

// Binary trees are constructed in order of post-order and middle-order, i.e. traversal in order of precedence.
void pre(int root,int start, int end, BTree& T) {
	// Note that root here is the index of root in Post
	// The division of two or so subtrees is in the Inorder, and all start and end are in the middle order.
	// Now find the root node in Inorder
	if (start > end) {
		T = NULL;
		return;
	}
	int i = start;
	while (i < end && Inorder[i] != Postorder[root]) i++;
	T = (BNode*)malloc(sizeof(BNode));
	T->left = T->right = NULL;
	T->data = Postorder[root];
	pre(root - end + i - 1, start, i - 1, T->left); // Left tree
	pre(root - 1, i + 1, end, T->right);            // Right subtree
}
void LevelTravel(BTree T) {
	// Hierarchical traversal of tree T
	queue<BTree> Q; // Traversing node queues
	Q.push(T);
	while (!Q.empty()) {
		BTree e;
		e = Q.front(); Q.pop();
		if (flag == 0) {
			printf(" ");
		}
		printf("%d", e->data);
		flag = 0;
		if (e->left) Q.push(e->left);
		if (e->right) Q.push(e->right);
	}
}
int main() {
	scanf("%d", &Len);
	int i;
	for (i = 0; i < Len; i++) scanf("%d", &Postorder[i]);
	for (i = 0; i < Len; i++) scanf("%d", &Inorder[i]);
	BTree T;
	pre(Len - 1, 0, Len - 1, T);
	LevelTravel(T);
	system("pause");
	return 0;
}