[UVA] 536 - Tree Recovery

題意:
拜訪樹有幾種方式:
前序(preorder):先拜訪根 再拜訪左子樹 最後拜訪右子樹=>根左右

中序(inorder):先拜訪左子樹 再拜訪根 最後拜訪右子樹=>左根右

後序(postorder):先拜訪左子樹 再拜訪右子樹 最後拜訪根=>左右根

這一題就是給你前序和中序，
要你求出後序。
--------------------------------------------
方法:
使用遞迴，
有前序就可以知道根，
再利用中序求出左子樹與右子樹，
以範例輸入:

前序DBACEGF 

中序ABCDEFG

由前序可以知道根是D，

知道根之後，可以在中序找到左子樹與右子樹的個數，

分別是3個,3個，

所以可以從前序知道根左右分別是D  , BAC  , EGF
分別對左子樹BAC和右子樹EGF做拜訪，
做完左樹與右樹的拜訪最後拜訪根，
就完成後序了。

---------------------------------------

/* 20150818
 * hanting
 * UVa 536 - Tree Recovery
 * C++
 */
#include <iostream>
using namespace std;
void travel(string &preord,string &inord,string &postord)
{
    if(preord.size())
    {
        string PreLeft,PreRight,InLeft,InRight;
        char root=preord[0];
        int FindRootInord=inord.find(root);

        InLeft=inord.substr(0,FindRootInord);
        InRight=inord.substr(FindRootInord+1);
        PreLeft=preord.substr(1,InLeft.size());
        PreRight=preord.substr(InLeft.size()+1);

        travel(PreLeft,InLeft,postord);//left
        travel(PreRight,InRight,postord);//right
        postord+=root;
    }
}
int main()
{
    string preord,inord;
    while(cin>>preord>>inord)
    {
        string postord="";
        travel(preord,inord,postord);
        cout<<postord<<endl;
    }
    return 0;
}