[UVA] 548 - Tree

題意:
給一棵樹的中序和後序，
求這棵樹的葉子到根節點的路徑權值總合最小的葉子。

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

方法:
建樹的過程跟536那題很像，
可以參考看看
536 - Tree Recovery
這題要做葉子的判斷就在於inord或postord的長度==1時就是葉子~
每找到一個子樹的root就去加上父節點的權值，
這樣找到葉子的時候就可以順便找到到root路徑上最小權值和的葉子了!

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

/* 20150822
 * hanting
 * UVa 548 - Tree
 * C++
 */
#include <iostream>
#include <vector>
#include <sstream>
#include <algorithm>//find
using namespace std;
istream& operator>>(istream& in,vector<int> &vec)
{
    vec.clear();
    string str;
    getline(in,str);
    stringstream sin(str);
    int num;
    while(sin>>num) vec.push_back(num);
    return in;
}
void FindLeaf(vector<int> &in,vector<int> &post,int &mini,int &ansLeaf,int parWeight)
{
    if(in.size()>1)
    {
        int root=post.back();
        vector<int>::iterator it=find(in.begin(),in.end(),root);//root position

        vector<int> inLeft(in.begin(),it);
        vector<int> inRight(it+1,in.end());
        vector<int> postLeft(post.begin(),post.begin()+inLeft.size());
        vector<int> postRight(post.begin()+inLeft.size(),post.end()-1);

        FindLeaf(inLeft,postLeft,mini,ansLeaf,root+parWeight);
        FindLeaf(inRight,postRight,mini,ansLeaf,root+parWeight);
    }
    else if(in.size()==1)//leaf
    {
        if(mini>in.back()+parWeight)
        {
            mini=in.back()+parWeight;
            ansLeaf=in.back();
        }
        else if(mini==in.back()+parWeight and in.back()<ansLeaf)
        {
            ansLeaf=in.back();
        }
    }
}
int main()
{
    vector<int> inord,postord;
    while(cin>>inord>>postord)
    {
        int mini=0x3fffffff;
        int ansLeaf=0;
        FindLeaf(inord,postord,mini,ansLeaf,0);
        cout<<ansLeaf<<endl;
    }
    return 0;
}