重建二叉树

题目：输入某二叉树的前序中序的遍历结果，重建出该二叉树。假设输入的前序和中序遍历中没有重复的数字。例如输入的前序遍历为{1，2，4，7，3，5，6，8}，中序遍历为{4，7，2，1，5，3，8，6}。
根据前序和中序遍历，构建出二叉树如下图：

后序遍历为：{7，4，2，5，8，6，3，1}。
思路：在二叉树的前序遍历中第一个数就是根节点。在中序遍历中根节点在中间，左子树的节点位于根节点的左边，右子树的节点在根节点的右边。因此我们需要扫描中序遍历找到根节点。
如图所示，根节点为1，扫面中序遍历找到根节点1，1左边的三个数，就是左子树的节点。1后面的4个数就是右子树的节点。接下来使用递归，逐渐建立二叉树。

代码如下：

            
                #include<iostream>
using namespace std;

struct BinaryTreeNode
{
    BinaryTreeNode()
    :_left(NULL), _right(NULL)
    {}
    int _value;
    BinaryTreeNode* _left;
    BinaryTreeNode* _right;
};

BinaryTreeNode* ConstructCore(int*StartPreOrder, int*EndPreOrder, int*StartInOrder, int*EndInOrder);

BinaryTreeNode* Construct(int*PreOrder, int*InOrder, intlength)
{
    if (PreOrder == NULL || InOrder == NULL || length <= 0)
        return NULL;
    elsereturn ConstructCore(PreOrder, PreOrder + length - 1, InOrder, InOrder + length - 1);
}

BinaryTreeNode* ConstructCore(int*StartPreOrder,int*EndPreOrder,int*StartInOrder,int*EndInOrder)
{
    int RootValue = StartPreOrder[0];
    BinaryTreeNode *root = new BinaryTreeNode();
    root->_value = RootValue;
    if (StartPreOrder == EndPreOrder)
    {
        //只有一个节点
        if (StartInOrder == EndInOrder && *StartPreOrder == *EndPreOrder)
            return root;
        elsereturn NULL;
    }
    //在中序遍历中找到根节点
    int*RootInOrder = StartInOrder;
    while (RootInOrder <= EndInOrder && *RootInOrder != RootValue)
        RootInOrder++;
    //没有找到根节点，中序遍历错误
    if (RootInOrder == EndInOrder && *RootInOrder != RootValue)
        return NULL;
    int LeftLen = RootInOrder - StartInOrder; //左子树的节点个数
    if (LeftLen > 0)
    {
        //构建左子树
        root->_left = ConstructCore(StartPreOrder + 1, StartPreOrder + LeftLen, StartInOrder, RootInOrder - 1);
    }
    if (LeftLen < (EndInOrder - StartInOrder))
    {
        //构建右子树
        root->_right = ConstructCore(StartPreOrder + LeftLen + 1, EndPreOrder, RootInOrder + 1, EndInOrder);
    }
    return root;
}

void PrintBackOrder(BinaryTreeNode *root)
{
    if (root)
    {
        PrintBackOrder(root->_left);
        PrintBackOrder(root->_right);
        cout << root->_value << "->";
    }
}

int main()
{
    int PreOrder[] = { 1, 2, 4, 7, 3, 5, 6, 8 };
    int InOrder[] = { 4, 7, 2, 1,5, 3, 8, 6 };
    int len = sizeof(PreOrder) / sizeof(PreOrder[0]);
    BinaryTreeNode *root = Construct(PreOrder, InOrder, len);
    PrintBackOrder(root);
    getchar();
    return0;
}