P1030 求先序排列

admin

https://www.luogu.org/problemnew/show/P1030
题目描述
给出一棵二叉树的中序与后序排列。求出它的先序排列。（约定树结点用不同的大写字母表示，长度<=8）。

输入输出格式
输入格式：
2行，均为大写字母组成的字符串，表示一棵二叉树的中序与后序排列。

输出格式：
1行，表示一棵二叉树的先序。

输入输出样例
输入样例#1：
BADC
BDCA
输出样例#1：

倚窗倾听风吹雨

1. #include<iostream>
   
2. using namespace std;
   
3. string sf,sa;
   
4. void w(string x,string y)
   
5. {
   
6.     if(x.size()<1)return;
   
7.     char ch=y[y.size()-1];
   
8.     cout<<ch;
   
9.     if(x.size()<=1)return;
   
10.     string x1,x2,y1,y2;
    
11.     int i=0;
    
12.     while(x[i]!=ch)
    
13.     {
    
14.         x1+=x[i];
    
15.         y1+=y[i];
    
16.         i++;
    
17.     }
    
18.     w(x1,y1);
    
19.     for(int j=i+1;j<x.size();j++)
    
20.     {
    
21.         x2+=x[j];
    
22.         y2+=y[j-1];
    
23.     }
    
24.     w(x2,y2);
    
25. }
    
26. int main()
    
27. {
    
28.     cin>>sf>>sa;
    
29.     w(sf,sa);
    
30.     return 0;
    
31. }
    

复制代码

黄煦喆

1. #include<iostream>
   
2. using namespace std;
   
3. string s,mid,bk;
   
4. void ms(string a,string b)
   
5. {
   
6.     if(a.size()>0)
   
7.     {
   
8.         int l=b.size();
   
9.         char ch=b[l-1];
   
10.         cout<<ch;
    
11.         int k=a.find(ch);
    
12.         ms(a.substr(0,k),b.substr(0,k));
    
13.         ms(a.substr(k+1),b.substr(k,a.size()-k-1));
    
14.     }
    
15. }
    
16. int main()
    
17. {
    
18.     cin>>mid>>bk;
    
19.     ms(mid,bk);
    
20.     return 0;
    
21. }
    

复制代码