面试题6：重建二叉树（根据前序和中序）

思路：

根据前序找到root，根据中序分开树的左右子树，然后左右子树各自递归

树：

struct BinaryTreeNode 
{
    int                    m_nValue; 
    BinaryTreeNode*        m_pLeft;  
    BinaryTreeNode*        m_pRight; 
};

递归实现

 1 BinaryTreeNode* ConstructCore(int* startPreorder, int* endPreorder, int* startInorder, int* endInorder);
 2 
 3 BinaryTreeNode* Construct(int* preorder, int* inorder, int length)
 4 {
 5     if(preorder == NULL || inorder == NULL || length <= 0)
 6         return NULL;
 7 
 8     return ConstructCore(preorder, preorder + length - 1,
 9         inorder, inorder + length - 1);
10 }
11 
12 BinaryTreeNode* ConstructCore
13 (
14     int* startPreorder, int* endPreorder, 
15     int* startInorder, int* endInorder
16 )
17 {
18     // 前序遍历序列的第一个数字是根结点的值
19     int rootValue = startPreorder[0];
20     BinaryTreeNode* root = new BinaryTreeNode();
21     root->m_nValue = rootValue;
22     root->m_pLeft = root->m_pRight = NULL;
23 
24     if(startPreorder == endPreorder)
25     {
26         if(startInorder == endInorder && *startPreorder == *startInorder)
27             return root;
28         else
29             throw std::exception("Invalid input.");
30     }
31 
32     // 在中序遍历中找到根结点的值
33     int* rootInorder = startInorder;
34     while(rootInorder <= endInorder && *rootInorder != rootValue)
35         ++ rootInorder;
36 
37     if(rootInorder == endInorder && *rootInorder != rootValue)
38         throw std::exception("Invalid input.");
39 
40     int leftLength = rootInorder - startInorder;
41     int* leftPreorderEnd = startPreorder + leftLength;
42     if(leftLength > 0)
43     {
44         // 构建左子树
45         root->m_pLeft = ConstructCore(startPreorder + 1, leftPreorderEnd, 
46             startInorder, rootInorder - 1);
47     }
48     if(leftLength < endPreorder - startPreorder)
49     {
50         // 构建右子树
51         root->m_pRight = ConstructCore(leftPreorderEnd + 1, endPreorder,
52             rootInorder + 1, endInorder);
53     }
54 
55     return root;
56 }