这里说一道很水的题……
通过后序遍历和中序遍历求前序遍历。
首先说一下这都是什么遍历方式……（蒟蒻已经全忘了）
简单地说，前序遍历就是访问根节点->左子树->右子树
中序遍历就是访问左子树-根节点-右子树
后序遍历则是访问左子树-右子树-根节点（当然以上规则是对于二叉树适用）
这样的话，我们就可以通过知道中，后序遍历求前序遍历，也可以知道前，中遍历求后序遍历，但是知道前后却不能求中序遍历，因为这棵树的结构并没有定型，会出现多种情况。
那我们怎么通过给定的中后序遍历求前序遍历呢？
首先，我们知道后续遍历的最后一个点必然是当前子树的根，那我们在中序遍历中找到这个根节点，之后，这个点两端的序列就分别对应根节点的左右子树的中序遍历序列。
之后我们发现……这两个中序遍历序列在后序遍历序列中，所对应的末尾的那一位仍然是当前子树（递归过一次）的根节点。
那我们只要一直递归求下去就可以，在没法继续递归的时候返回。
看一下代码（超级短，知道前中求后序同理）
#include<cstring> #include<iostream> #include<cstdio> using namespace std; string s1,s2; void build(int l1,int r1,int l2,int r2) { printf("%c",s2[r2]); int m = s1.find(s2[r2]); if(m > l1) build(l1,m - 1,l2,r2 + m - r1 - 1); if(m < r1) build(m + 1,r1,r2 + m - r1,r2 - 1); } int main() { cin>>s1>>s2; build(0,s1.length() - 1,0,s2.length() - 1); putchar('\n'); return 0; }