题目描述：

二叉树的前序、中序、后序遍历的定义：
前序遍历：对任一子树，先访问跟，然后遍历其左子树，最后遍历其右子树；
中序遍历：对任一子树，先遍历其左子树，然后访问根，最后遍历其右子树；
后序遍历：对任一子树，先遍历其左子树，然后遍历其右子树，最后访问根。
给定一棵二叉树的前序遍历和中序遍历，求其后序遍历（提示：给定前序遍历与中序遍历能够唯一确定后序遍历）。

输入：

两个字符串，其长度n均小于等于26。
第一行为前序遍历，第二行为中序遍历。
二叉树中的结点名称以大写字母表示：A，B，C....最多26个结点。

输出：

输入样例可能有多组，对于每组测试样例，
输出一行，为后序遍历的字符串。

样例输入：

ABC
BAC
FDXEAG
XDEFAG

样例输出：

BCA
XEDGAF

代码：

#include <iostream>  
#include <cstring>   
using namespace std;  
char preString[26],inString[26];  
int BiTree[27][2];//[结点][0=l，1=r]   
void partition(int preStart,int preEnd,int inStart,int inEnd);  
void postOrder(int root);  

int main(){  
    int root;  
    while (cin>>preString){  
        cin>>inString;  
        //initiate  
        //process  
        partition(0,strlen(preString)-1,0,strlen(inString)-1);  
        //output  
        postOrder(preString[0]-'A');  
        cout<<endl;  
    }  
    return true;  
}  

void partition(int preStart,int preEnd,int inStart,int inEnd){  
    for (int count=0;count<inEnd-inStart+1;count++){  
        if (inString[count+inStart]==preString[preStart]){//若找到了此子树的根   
            //left  
            if (count!=0){//lc!=NULL  
                BiTree[inString[count+inStart]-'A'][0]=preString[preStart+1]-'A';  
                partition(preStart+1,preStart+count,inStart,inStart+count-1);  
            }  
            else{  
                BiTree[inString[count+inStart]-'A'][0]=-1;  
            }  
            //right  
            if (count!=inEnd-inStart){//rc!=NULL  
                BiTree[inString[count+inStart]-'A'][1]=preString[preStart+count+1]-'A';  
                partition(preStart+count+1,preEnd,inStart+count+1,inEnd);  
            }  
            else{  
                BiTree[inString[count+inStart]-'A'][1]=-1;  
            }  
        }  
    }  
}  

void postOrder(int root){  
    if (BiTree[root][0]!=-1)  
        postOrder(BiTree[root][0]);  
    if (BiTree[root][1]!=-1)      
        postOrder(BiTree[root][1]);  
    cout<<(char)(root+'A');  
}

作者提醒：

据机试指南说本题包括了建树、遍历、还原等多个考点，几乎涉及机试二叉树所有考点。
所以吃透此题就好棒棒。
写完此题后与机试指南上一对照，应该说两种方法在大体思路上别无二致。
区别在于机试指南采用了具体的二叉树结构，而我的代码使用了一个二维数组来存储二叉树的游标，
并没有定义具体的二叉树结构体，这是出于节省时空的考虑，故抽象度更高。
再加上数据结构有点生疏了，写起来确实费了一番功夫。写的时间主要花在了下标＋－的处理上＝皿＝
通过前序中序还原二叉树的关键就在于：找到根节点后，
对左子树序列和右子树序列用同样的方法递归找根。刚开始写的时候本想递归传字符串，
后来发现还是传start end 游标来的效率高一些。