洛谷--P1827 [USACO3.4]美国血统 American Heritage

思路

我们可以根据前序遍历和中序遍历的特点来找出后续遍历，前序遍历的第一个结点就是根节点，然后根据这个根节点去把中序遍历划分为两个集合，左边就是左子树，右边就是右子树。

AC代码

#include<iostream>#include<cstring>#include<algorithm>using namespace std;string preStr,midStr;void dfs(string a,string b){//a字符串是中序遍历，b字符串是前序遍历if(a.size()==0)return;int index=a.find(b[0]);dfs(a.substr(0,index),b.substr(1,index));//递归左边dfs(a.substr(index+1),b.substr(index+1));//递归右边cout<<b[0];//后序遍历是左右根}int main(){cin>>midStr>>preStr;dfs(midStr,preStr);return 0;}