給一個二叉樹前序遍歷和中序遍歷的結(jié)果，請重建這顆二叉樹。例如前序遍歷結(jié)果為：
{1,2,4,7,3,5,6,8}，中序遍歷結(jié)果為{4,7,2,1,5,3,8,6}。

算法思路：由于前序遍歷的第一個一定是根節(jié)點，故可以從前序遍歷結(jié)果中確定一個根節(jié)點，所以此二叉樹的根節(jié)點是1。根據(jù)中序遍歷先訪問左節(jié)點，再訪問根節(jié)點，最后訪問右節(jié)點的特點，根節(jié)點一定是在左節(jié)點和右節(jié)點之間，故可以在中序遍歷中找到根節(jié)點，將剩下的分割為左邊節(jié)點部分和右邊節(jié)點部分，比如在上述中序遍歷中找到1后，可以將{4,7,2}作為1的左節(jié)點部分，{5,3,8,6}作為1的右節(jié)點部分。確定好這兩部分的長度后，再將先序遍歷結(jié)果分割為兩部分，一部分是{2,4,7}，另一部分是{3,5,6,8}，再分別對分割后的序列{2,4,7}和{4,7,2}，{3,5,6,8}和{5,3,8,6}重復(fù)上述操作（遞歸）。

由題干得，函數(shù)傳入的參數(shù)應(yīng)為前序遍歷結(jié)果和中序遍歷結(jié)果，還應(yīng)該有個序列長度，來確定起始位置。

BinaryTreeNode* Construct(int* preorder,int* inorder,int length)
{
    if(preorder == nullptr || inorder == nullptr || length <= 0)
        return;
    else
        return ConstructCore(preorder,preorder + length -1,inorder,inorder + length -1);
}

BinaryTreeNode* ConstructCore(int* startPreorder,int* endPreorder,int* startInorder,int* endInorder)
{
    int rootvalue = startPreorder[0];
    BinaryTreeNode* pNew = new BinaryTreeNode();
    pNew -> m_nvalue = rootvalue;
    pNew -> m_pLeft = pNew -> m_pRright = nullptr;

    if(startPreorder == endPreorder)
    {
        if(startInorder = endInorder && *startPreorder = *startInorder)
        {
            return root;
        }   
        else
        {
            throw std::exception("Invalid input");
        }
    }

    int* rootInorder = startInorder;
    while(rootInorder != rootvalue && rootInorder <= endInorder)
        rootInorder++;
    if(rootInorder == endInorder && *rootInorder != rootvalue)
        throw std::exception("Invalid input")
    //確定分割長度
    int left_length = rootInorder - startInorder; 
    int* leftPreorderEnd = startPreorder + left_length; //確定先序遍歷中分割的部分
    if(left_length > 0)
    {
        root -> m_pLeft = ConstructCore(startPreorder+1,leftPreorderEnd,startInorder,rootInorder-1);
    }

    if(left_length < endPreorder - startPreorder)
    {
        root -> m_pRright = ConstructCore(leftPreorderEnd+1,endPreorder,rootInorder+1,endInorder);
    }
    return root;
}