3021: 【普及-】【P1030】求先序排列
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：3
解决：2
题目描述
给出一棵二叉树的中序与后序排列。求出它的先序排列。（约定树结点用不同的大写字母表示，且二叉树的节点个数 ）。
输入
共两行，均为大写字母组成的字符串，表示一棵二叉树的中序与后序排列。
输出
共一行一个字符串，表示一棵二叉树的先序。
样例输入 复制
BADC
BDCA样例输出 复制
ABCD提示
#include<bits/stdc++.h>
using namespace std;
void dfs(string s1, string s2) {
char root=s2[s2.size()-1];
int l = s1.find(root),r = s1.size() - l - 1;
cout << root;
if(l){
string s1_l = s1.substr(0,l), s2_l=s2.substr(0,l);
dfs(s1_l,s2_l);
}
if(r){
string s1_r=s1.substr(l+1,r), s2_r=s2.substr(l,r);
dfs(s1_r,s2_r);
}
}
int main(){
string s1,s2;
cin>>s1>>s2;
dfs(s1,s2);
return 0;
}