【2001NOIP普及组】T3. 求先序排列 试题解析
时间限制: 1000 ms 内存限制: 65536 KB
【题目描述】
给出一棵二叉树的中序与后序排序。求出它的先序排列。（约定树结点用不同的大写字母表示，长度≤8）。
【输入】
一行,一棵二叉树的中序与后序排序,中间用一个空格隔开。
【输出】
它的先序排列
【输入样例】
BADC BDCA
【输出样例】
ABCD
试题解析：递归 树 中序、后序转先序
1. #include<bits/stdc++.h> 2. using namespace std; 3. string a,b; 4. void build(int l1,int r1,int l2,int r2){ 5. int m=a.find(b[r2]); 6. int n=b.find(b[r2]); 7. cout<<b[r2]; 8. if(m>l1) build(l1,m-1,n-1,m-1); 9. if(m<r2) build(m+1,r1,m,r2-1); 10. } 11. void build(string mid,string back) 12. { 13. int m = mid.find(back[back.size()-1]); 14. cout<<back[back.size()-1]; 15. if(m>0) build(mid.substr(0,m),back.substr(0,m)); 16. if(m+1<mid.size()) build(mid.substr(m+1),back.substr(m,back.size()-m-1)); 17. } 18. int main() 19. { 20. cin>>a>>b; 21. //build(0,a.size()-1,0,b.size()-1); 22. build(a,b); 23. return 0; 24. }
