Output first order traversal according to second order and middle order traversal (25 points)

This problem requires that according to the post order traversal and middle order traversal results of a given binary tree , Output the pre order traversal result of the tree .

Input format :

The first line gives a positive integer N(≤30), Is the number of nodes in the tree . The next two lines , Each line gives N It's an integer , Corresponding to post order traversal and middle order traversal results respectively , Numbers are separated by spaces . The title ensures that the input is correct and corresponds to a binary tree .

Output format :

Output in one line Preorder:  And the pre order traversal result of the tree . Between the numbers 1 A space , 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 :

Preorder: 4 1 3 2 6 5 7

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <queue>
#include<map>
using namespace std;

const int N = 40;

int n,count1;
int postorder[N], inorder[N];               // The former sequence traversal , In the sequence traversal 
unordered_map<int, int> l, r, pos;          // Simulating binary tree with hash table 

int build(int il, int ir, int pl, int pr)
{
	int root = postorder[pr];
	int k = pos[root];                      // Get the subscript of the root node in the middle order traversal 
	
	//k Greater than il Indicates that there are nodes on the left of the root node , That is, the current root node has a left subtree , The same below 
	// Here are two difficult lines , See the figure for example 
	if (il < k) l[root] = build(il, k - 1, pl, pl + k - 1 - il);
	if (ir > k) r[root] = build(k + 1, ir, pl + k - il, pr - 1);
	
	return root;
}

void dfs(int root)                          //BFS Used to traverse the output 
{
    if(count1==0)
    cout<<root;
    else cout<<" "<<root;
    count1++;
    if(l.count(root))dfs(l[root]);
    if(r.count(root))dfs(r[root]);
}

int main()
{
	cin >> n;
	for (int i = 0; i < n; i ++ ) cin >> postorder[i];
	for (int i = 0; i < n; i ++ )
	{
		cin >> inorder[i];
		pos[inorder[i]] = i;                // Record the position of each point in sequence （ prune ）
	}
	
	int root = build(0, n - 1, 0, n - 1);   // The parameters are middle order traversal interval and post order traversal interval 
    printf("Preorder: ");
	dfs(root);
	
	return 0;
}