Binary tree topic -- p1030 [noip2001 popularization group] find the first order

[NOIP2001 Popularization group ] Find the precedence

Title Description

In this paper, we give the middle order and the back order of a binary tree . Find out its precedence .（ Convention tree nodes are represented by different capital letters , length $ \le 8$）.

Input format

$2$ That's ok , A string of uppercase letters , Represents the middle and back order of a binary tree .

Output format

$1$ That's ok , Represents the precedence of a binary tree .

Examples #1

The sample input #1

BADC
BDCA

Sample output #1

ABCD

Tips

【 Title source 】

NOIP 2001 Third question of popularization group

#define _CRT_SECURE_NO_WARNINGS 1
#include <bits/stdc++.h>

using namespace std;
//#define int long long
//#define map unordered_map
const int N = 10;
map<char, int> l, r, d;
char in[N], post[N];

int dfs1(int il, int ir, int pl, int pr)
{
    
	if (pl > pr) return -1;
	char root = post[pr];
	int k = d[root];
	l[root] = dfs1(il, k - 1, pl, k - 1 - il + pl);
	r[root] = dfs1(k + 1, ir, k - il + pl, pr - 1);
	return k;
}

void dfs2(int u)
{
    
	if (u == -1) return;
	cout << in[u];
	if (l[in[u]] != -1) dfs2(l[in[u]]);
	if (r[in[u]] != -1) dfs2(r[in[u]]);
}

signed main()
{
    
	int T = 1; //cin >> T;

	while (T--)
	{
    
		cin >> in >> post;
		for (int i = 0; in[i]; ++i)
		{
    
			d[in[i]] = i;
		}
		int n = strlen(in);
		int root = dfs1(0, n - 1, 0, n - 1);
		dfs2(root);
		puts("");
	}

	return 0;
}