劍指Offer 4：重建二叉樹

Description

輸入某二叉樹的前序周遊和中序周遊的結果，請重建出該二叉樹。假設輸入的前序周遊和中序周遊的結果中都不含重複的數字。例如輸入前序周遊序列{1,2,4,7,3,5,6,8}和中序周遊序列{4,7,2,1,5,3,8,6}，則重建二叉樹并傳回。

Solution:

兩個周遊序列的特點：

• 前序周遊：root，左子樹，右子樹
• 中序周遊：左子樹，root，右子樹

依此，我們可以先在前序中得到root，然後在中序中将左子樹和右子樹分開，進而得到在兩個子樹的前序周遊和中序周遊。最後遞歸得到整個二叉樹。

//C++
    TreeNode* reConstructBinaryTree(vector<int>& pre,vector<int>& vin) {
        if(pre.empty() || vin.empty())    return NULL;
        return helper(pre, vin, 0, pre.size(), 0, vin.size());
    }
    //ps: pre中的開始index
    //pe: pre中的結束index
    //is：vin中的開始index
    //ie：vin中的結束index
    //兩個區間均為左閉右開
    TreeNode* helper(const vector<int>& pre, const vector<int>& vin, 
    				int ps, int pe, int is, int ie){
        if(ps >= pe || is >= ie)    return NULL;
        TreeNode* root = new TreeNode(pre[ps]);
        //search
        for(int i = is; i < ie; ++i){
            if(vin[i] == pre[ps]){
                root->left = helper(pre, vin, ps+1, ps + i - is + 1, is, i);
                root->right = helper(pre, vin, ps + i - is + 1, pe, i+1, ie);
                break;
            }
        }
        return root;
    }