Description
树和二叉树基本上都有先序、中序、后序、按层遍历等遍历顺序，给定中序和其它一种遍历的序列就可以确定一棵二叉树的结构。
假定一棵二叉树一个结点用一个字符描述，现在给出中序和按层遍历的字符串，求该树的先序遍历字符串。
Analysis
我们先前做过 给定前序中序求后序，核心思想是 找root，也就是树根，然后递归处理。不妨本题借鉴如上做法。
所谓 “层次序列”，实际上就是 bfs 序。通过 bfs 序，我们可以很轻松的找到树根。下方给出一个样例，编号为 bfs 序。
容易发现，当前的 root 即为当前 bfs 编号最小的数。找到树根后，和求后序同理，尝试在中序中找到该节点，将其分为左右两个子树。分别递归处理即可。
原理如上，实现的时候需要注意一些细节，具体如下。
-
进行搜索树根的时候，如果搜到一个最小的树根，我们需要判断它是否在当前子树内，如果不在当前子树内则它不合法。就应当找另外一个根。
-
递归搜索左右子树的时候，需要特判越界。否则会死循环。
AC Code
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
using namespace std;
const int N = 10010;
string bet,bfs;
bool flag[N];
void dfs(int l,int r)
{
int pos;
for(int i=0;i<bfs.size();i++)
{
if(!flag[i])
{
for(int j=l;j<=r;j++)
{
if(bfs[i] == bet[j])
{
pos = j;
flag[i] = 1;
break;
}
}
if(flag[i])
{
break;
}
}
}
cout<<bet[pos];
if(l < pos && r > pos)
dfs(l,pos-1);
if(r > pos)
dfs(pos+1,r);
}
int main()
{
freopen("input.txt","r",stdin);
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>bet>>bfs;
dfs(0,bet.size()-1);
}