A38150. 重建二叉树给定一棵二叉树的前序遍历和中序遍历的结果，求其后序遍历。输入输入可能有多组，以EOF结束。 每组输入包含两个字符串，分别为树的前序遍历和中序遍历。每个字符串中只包含大写字母且互不重复。输出对于每组输入，用一行来输出它后序遍历结果。样例输入DBACEGF ABCDEFGBCAD CBAD样例输出ACBFGEDCDAB样例输入DBACEGF ABCDEFGBCAD CBAD样例输出ACBF…
填空题
困难
知识点
题目描述
重建二叉树
给定一棵二叉树的前序遍历和中序遍历的结果，求其后序遍历。
输入
输入可能有多组，以EOF结束。 每组输入包含两个字符串，分别为树的前序遍历和中序遍历。每个字符串中只包含大写字母且互不重复。
输出
对于每组输入，用一行来输出它后序遍历结果。
样例输入
DBACEGF ABCDEFG
BCAD CBAD
样例输出
ACBFGED
CDAB
样例输入
DBACEGF ABCDEFG
BCAD CBAD
样例输出
ACBFGED
CDAB
参考答案
#include <bits/stdc++.h>
using namespace std;
char a[30],b[30];
string ta,tb;
int la,lb;
void build(int l1,int r1,int l2,int r2){
int m=tb.find(ta[l1]);
if(m>l2)build(l1+1,l1+m-l2,l2,m-1);
if(m<r2)build(l1+m-l2+1,r1,m+1,r2);
cout<<ta[l1];
}
int main()
{
while(scanf("%s",a)!=EOF){
scanf("%s",b);
ta=string(a);
tb=string(b);
build(0,ta.size()-1,0,tb.size()-1);
cout<<endl;
}
return 0;
}
上一题
下一题