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