关于知道后序序列和中序序列确定前序序列

以下是大神的解释  摘自洛谷题解， 比较清晰

DEBAFCG

EDBFGCA

首先这棵树的根是A（后序排列的最后一个），输出A；

然后在中序排列中找到A的位置，发现它左右各有三个点，分别是它的左右子树；

把中序排列左边三个点和后序排列的前三个点作为左子树去dfs，因为先序排列是中-左-右，所以先走左边；

> [L]传入的中序是DEB，后序是EDB - 输出B，DE是左子树，同样操作；

>> [L]传入的中序是DE，后序是ED - 输出D，E是右子树，同样操作；

>>> [R]传入的中序是E，后序是E - 输出E；

> [R]传入的中序是FCG，后序是FGC - 输出C，F是左子树，同样操作，G是右子树，同样操作；

>> [L] 传入的中序是F，后序是F - 输出F；

>> [R] 传入的中序是G，后序是G - 输出G；

这样我们就完成了求先序遍历的过程。（上面略去了L/R子树为空的场合。

以下为代码实现

#include <iostream>  
#include <cstring>  
#include <iomanip>  
#include <cstdio>  
#include <string>  
#include <algorithm>  
#include <queue>  
#include <cmath>  
#include <map>  
using namespace std;  
string mid;  
string last;  
void dfs(int l,int r,int z,int y)  
{  
    if(l>r||z>y) return ;  
    cout<<last[y];  
    for(int i=l;i<=r;i++)  
    {  
        if(last[y]==mid[i])  
        {  
            dfs(l,i-1,z,z+i-l-1);  
            dfs(i+1,r,z+i-l,y-1);  
        }  
    }  
}  
int main()  
{  
    cin>>mid;  
    cin>>last;  
    int l=strlen(&mid[0]);  
    dfs(0,l-1,0,l-1);  
}