6.重建二叉树（代码未完成）

  题目：输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1，2，4，7，3，5，6，8}和中序遍历序列{4，7，2，1，5，3，8，6}，则重建出图2.6所示的二叉树并输出它的头结点。

  思路：因为前序遍历先访问根结点，所以我们可以从前序遍历序列中先找到根结点1，然后中序遍历先访问左子结点，再访问根结点，最后访问右子结点。所以根结点1的左边为左子树结点，右边为右子树结点。以此类推，通过递归可重建该二叉树。

  测试用例:
  1.普通二叉树（完全二叉树，不完全二叉树）。
  2.特殊二叉树（所有结点都没有右子结点的二叉树，没有左子结点的二叉树，只有一个结点的二叉树）。
  3.特殊输入测试（二叉树的根结点指针为NULL，输入的前序遍历序列和中序遍历序列不匹配）。

1#include<iostream>
2#include<cstdio>
3using namespace std;
4
5struct BinaryTreeNode
6{
7    int                 m_nValue;
8    BinaryTreeNode*     m_pLeft;
9    BinaryTreeNode*     m_pRight;
10};
11
12BinaryTreeNode* ConstructCore(int* startPreorder, int* endPreorder,
13                              int* startInorder, int* endInorder)
14{
15    //前序遍历序列的第一个数字是根结点的值
16    int rootValue = startPreorder[0];
17    BinaryTreeNode* root = new BinaryTreeNode();
18    root->m_nValue = rootValue;  //将值赋给头结点
19    root->m_pLeft = root->m_pRight = NULL; //把左右结点值设NULL
20
21    if (startPreorder == endPreorder)  //前序遍历的头结点和尾结点相等，说明只有一个节点
22    {
23        if (startInorder == endInorder && *startPreorder == *startInorder)
24        {
25            return root;
26        }
27        else
28        {
29            throw exception("invalid input!");
30        }
31    }
32
33    //在中序遍历中找到根结点的值
34    int* rootInorder = startInorder;
35    while (rootInorder <= endInorder && *rootInorder != rootValue)
36    {
37        ++rootInorder;
38    }
39
40    if (rootInorder == endInorder && *rootInorder != rootValue)
41    {
42        throw exception("invaild input!");
43    }
44
45    int leftLength = rootInorder - startInorder;
46    int* leftPreorderEnd = startPreorder + leftLength;
47    if (leftLength > 0)
48    {
49        //构建左子树
50        root->m_pLeft = ConstructCore(startPreorder + 1, leftPreorderEnd,
51                                       startInorder, rootInorder - 1);
52    }
53
54    if (leftLength < endPreorder - startPreorder)
55    {
56        // 构建右子树
57        root->m_pRight = ConstructCore(leftPreorderEnd + 1,
58                                       endPreorder, rootInorder + 1, endInorder);
59    }
60
61    return root;
62}
63
64BinaryTreeNode* Construct(int* preorder, int* inorder, int length)
65{
66    if (preorder == NULL) || inorder == NULL || length <= 0)
67    {
68        return NULL;
69    }
70
71    return ConstructCore(preorder, preorder + length - 1, inorder,
72                         inorder + length - 1);
73
74}