1828-求后序遍历

利用树是递归定义的，用递归的方式访问二叉树。
二叉树三种遍历对应三种递归方式：

//先序遍历
void dfs(...)
{
   访问当前子树根节点;
   if(左子树存在) dfs(左子树);
   if(右子树存在) dfs(右子树);
}

//中序遍历
void dfs(...)
{
   if(左子树存在) dfs(左子树);
   访问当前子树根节点;
   if(右子树存在) dfs(右子树);
}

//后序遍历
void dfs(...)
{
   if(左子树存在) dfs(左子树);
   if(右子树存在) dfs(右子树);
   访问当前子树根节点;
}

现在不知道二叉树的存储方式，只告诉我们先序遍历序列和中序遍历序列，那么该如何遍历？
首先明白，中序遍历如果知道根在哪里，就可以划分成左右子树，然后可以继续递归左右子树，终点是当前的根节点不知道，而先序遍历恰恰知道根节点位置，因为先序遍历的顺序是：根左右。
所以可以通过先序遍历确定根节点编号，再根据根节点把中序遍历划分成左右子树。
需要注意的是，要想继续遍历，必须计算出左右子树的先序遍历和中序遍历，这步是做这题的关键。

根据后序遍历顺序（左右根），输出：$debca$
树是递归定义的，为了确定遍历序列，可以用区间的方式定义序列。

void dfs(int l1, int r1,int l2, int r2)
{
	int root = s2.find(s1[l1]);  //s1[l1]为当前子树的根
	if(l2<root) dfs(l1+1,l1+root-l2,l2,root-1);
	if(root<r2) dfs(l1+root-l2+1,r1,root+1,r2);
	cout<<s1[l1];                //左右根，前面遍历了左右子树，所以这里输出子树的根
}

关于区间位置的计算，需要耐心的打草稿。

cin>>s1>>s2;  //s1前序遍历序列  s2中序遍历序列
dfs(0,s1.size()-1,0,s2.size()-1);