1364：二叉树遍历(flist)
时间限制: 1000 ms 内存限制: 65536 KB
【题目描述】
树和二叉树基本上都有先序、中序、后序、按层遍历等遍历顺序，给定中序和其它一种遍历的序列就可以确定一棵二叉树的结构。
假定一棵二叉树一个结点用一个字符描述，现在给出中序和按层遍历的字符串，求该树的先序遍历字符串。
【输入】
两行，每行是由字母组成的字符串（一行的每个字符都是唯一的），分别表示二叉树的中序遍历和按层遍历的序列。
【输出】
一行，表示二叉树的先序序列。
【输入样例】
DBEAC
ABCDE
【输出样例】
ABDEC
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; string in,level;//int中序遍历 level层序遍历 void preorder(int l1,int r1,int l2,int r2){ int pos; for(int i=l2;i<=r2;i++){ int flag=0; for(int j=l1;j<=r1;j++){ if(level[i]==in[j]){//找根 cout<<in[j]; pos=j; flag=1; break; } } if(flag) break; } if(pos>l1) preorder(l1,pos-1,l2,r2); if(pos<r1) preorder(pos+1,r1,l2,r2); } int main() { cin>>in>>level; preorder(0,in.length()-1,0,level.length()-1); return 0; }
