原题地址：

题目描述：

二叉树的前序、中序、后序遍历的定义：

前序遍历：对任一子树，先访问跟，然后遍历其左子树，最后遍历其右子树；

中序遍历：对任一子树，先遍历其左子树，然后访问根，最后遍历其右子树；

后序遍历：对任一子树，先遍历其左子树，然后遍历其右子树，最后访问根。

给定一棵二叉树的前序遍历和中序遍历，求其后序遍历（提示：给定前序遍历与中序遍历能够唯一确定后序遍历）。

输入：

两个字符串，其长度n均小于等于26。

第一行为前序遍历，第二行为中序遍历。

二叉树中的结点名称以大写字母表示：A，B，C....最多26个结点。

输出：

输入样例可能有多组，对于每组测试样例，

输出一行，为后序遍历的字符串。

样例输入：

ABCBACFDXEAGXDEFAG

样例输出：

BCAXEDGAF

来源：

已知前序、中序求后序，或者已知中序、后序求前序，都是典型的二叉树的应用。

直接用测试数据解释比较方便：

已知前序、中序序列，求后序序列的基本步骤如下：

1. 在前序序列pre[s1, e1]中的第一个元素一定是现在正在构造的树的根节点root

2. 在中序序列mid[s2, e2]中找到这个元素的位置rootIndex，在rootIndex两侧的序列即这个root左右子树的中序序列

3. 根据子串长度回到前序序列中确定这两个左右子树的前序序列

4. 递归上述过程，由左子树的前序序列和中序序列建立左子树，由右子树的前根序序列和中根序序列建立右子树；

5. 返回树根root。

类似地，已知中序、后序序列，求前序序列，只是上面的第一步改为取后序序列的最后一个元素，其余步骤一致。

AC代码如下：（附中序后序求前序的代码，已注释）

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #define MAXN 30using namespace std;typedef struct node{    char c;    node *lchild, *rchild;}NODE;char preStr[MAXN]; //前序遍历序列char midStr[MAXN]; //中序遍历序列char posStr[MAXN]; //后序遍历序列//s1/e1为前序字符串的首尾,s2/e2为中序字符串首尾NODE* BuildTree_PreMid(int s1, int e1, int s2, int e2)//通过前序字符串和中序字符串，建立二叉树{    NODE* newNode = (NODE*)malloc(sizeof(NODE));    newNode->lchild = newNode->rchild = NULL;    newNode->c = preStr[s1]; //前序的第一个为根节点    int rootIndex = -1;    for (int i = s2; i<=e2; ++i)    {        if (midStr[i] == preStr[s1]) //找到中序序列中的当前根节点对应下标        {            rootIndex = i;            break;        }    }    //注意下面递归式参数的计算    if (rootIndex != s2) //中序的左边还有元素，即存在左子树        newNode->lchild = BuildTree_PreMid(s1+1, s1+(rootIndex-s2), s2, rootIndex-1);    if (rootIndex != e2) //中序的右边还有元素，即存在右子树        newNode->rchild = BuildTree_PreMid(s1+(rootIndex-s2)+1, e1, rootIndex+1, e2);    return newNode;}//s1/e1为中序字符串的首尾,s2/e2为后序字符串首尾NODE* BuildTree_MidPos(int s1, int e1, int s2, int e2)//通过中序字符串和后序字符串，建立二叉树{    NODE* newNode = (NODE*)malloc(sizeof(NODE));    newNode->lchild = newNode->rchild = NULL;    newNode->c = posStr[e2];    int rootIndex = 0;    for (int i = s1; i <= e1; ++i) //找到中序序列中的当前根节点对应下标    {        if (midStr[i] == posStr[e2])        {            rootIndex = i;            break;        }    }    if (rootIndex != s1) //中序的左边还有元素，即存在左子树        newNode->lchild = BuildTree_MidPos(s1, rootIndex-1, s2, s2+(rootIndex-s1)-1);    if (rootIndex != e1) //中序的右边还有元素，即存在右子树        newNode->rchild = BuildTree_MidPos(rootIndex+1, e1, s2+(rootIndex-s1) ,e2-1);    return newNode;}void preOrder(NODE* t) //前序遍历{    if (t != NULL)    {        cout << t->c;        preOrder(t->lchild);        preOrder(t->rchild);    }}void midOrder(NODE* t) //中序遍历{    if (t != NULL)    {        midOrder(t->lchild);        cout << t->c;        midOrder(t->rchild);    }}void posOrder(NODE* t) //后序遍历{    if (t != NULL)    {        posOrder(t->lchild);        posOrder(t->rchild);        cout << t->c;    }}int main(){    //已知前序、中序求后序    while (cin >> preStr)    {        cin >> midStr;        NODE* root = NULL;        root = BuildTree_PreMid(0, strlen(preStr)-1, 0, strlen(midStr)-1); //建树        posOrder(root);        cout << endl;    }    /*    //已知中序、后序求前序    while (cin >> midStr)    {        cin >> posStr;        NODE* root = NULL;        root = BuildTree_MidPos(0, strlen(midStr)-1, 0, strlen(posStr)-1); //建树        preOrder(root);        cout << endl;    }    */    return 0;}
       
      
     
    

内存占用：1520Kb 耗时：10ms

算法复杂度：O(n)