输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序序列和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建该二叉树并返回它的头结点。
二叉树的节点定义如下：
1
2
3
4
5
6
| struct BinaryTreeNode
{
int m_nValue; //data域
BinaryTreeNode* m_pleft; //左孩子的指针
BinaryTreeNode* m_pright; //右孩子的指针
}
|
问题分析：
在二叉树的前序遍历序列中，第一个数字总是树的根结点的值。但在中序遍历中，根结点的值在序列的中间，左子树的节点的值位于根结点的值的左边，而右子树的结点的值位于根结点的值的右边。因此，需要扫描中序遍历序列，才能找到根结点的值。
通过上述步骤可以得到根结点以及左右子树的先序遍历序列和中序遍历序列，通过递归可以使用同样的方法分别构建左右子树。
代码实现（C/C++）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
| BinaryTreeNode* Construct(int* preoder,int* inorder,int length)
{
if(preorder==NULL || inorder==NULL || length<=0)
return NULL;
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* root=new BinaryTreeNode();
root->m_nValue=rootValue;
root->m_pLeft=root->m_pRight=NULL;
if(startPreorder==endPreoder){
if(startInorder==endInorder && *startPreorder==*startInorder)
return root;
else
throw std::exception("Invalid input.");
}
//中序遍历中找到根结点的值
int* rootInorder=startInorder;
while(rootInorder<=endInorder && *rootInorder!=rootValue)
++rootInorder;
if(rootInorder==endInorder && *rootInorder!=rootValue)
throw std::exception("Invalid input.");
int leftLength=rootInorder-startInorder;
int* leftPreorderEnd=startPreorder+leftLength;
//构建左子树
if(leftLength>0){
root->m_pLeft=ConstructCore(startPreorder+1,leftPreorderEnd,startInorder,rootInorder-1);
}
//构建右子树
if(leftLength<endPreorder-startPreorder){
root->m_pRight=ConstructCore(leftPreorderEnd+1,endPreorder,rootInorder,endInorder);
}
return root;
}
|
这里定义的ConstructCore中，先根据前序遍历序列中的第一个数字创建根结点，接下来在中序遍历中找到根结点的位置，这样就能确定左右子树结点的数量。在前序遍历和中序遍历中划分左右子树结构的值后，用ConstructCore递归地调用，构建左右子树。