美国血统

题目

已知一棵二叉树的中序遍历和前序遍历 求后序遍历

输入输出格式

输入格式

第一行: 树的中序遍历

第二行: 同样的树的前序遍历

输出格式

单独的一行表示该树的后序遍历。

输入输出样例

输入样例

ABEDFCHG

CBADEFGH

输出样例

AEFDBHGC

思路

递归

根据前序遍历找根 然后分割中序遍历 每次先遍历左子树再遍历右子树 然后输出分割点

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#define Max(x, y) (x >= y ? x : y)
#define Min(x, y) (x <= y ? x : y)
#define F(i, x, y) for(register int i=x; i<=y; i++)
#define R(i, x, y) for(register int i=x; i>=y; i--)
using namespace std;
inline void in(int &x)
{
static int ch; static bool flag;
for(flag=false, ch=getchar(); ch<'0'||ch>'9'; ch=getchar()) flag |= ch=='-';
for(x=0; isdigit(ch); ch=getchar()) x = (x<<1) + (x<<3) + ch - '0';
x = flag ? -x : x;
}
char a[30], b[30];
int len, id=1;
void build(int l, int r, int lb, int rb)
{
if (l > r || lb > rb) {return ;}
F(i, l, r) if (a[i] == b[lb])
{
build(l, i-1, lb+1, lb+i-l);
build(i+1, r, lb+i-l+1, rb);
cout<<a[i];
}
}
inline int work()
{
scanf("%s", a+1); scanf("%s", b+1);
len = strlen(a+1);
build(1, len, 1, len);
return 0;
}
int TAT = work();
int main() {;}