重建二叉树（剑指offer第四题）
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
思路
递归重建二叉树。每次递归，在中序序列中寻找此时对应先序序列的首元素。然后以此元素为界划分中序序列为左右两个子序列L1，L2；先序序列以L1和L2的长度同样划分为左右两个子序列。然后对应中序序列与先序序列的左右子序列继续递归，直至无法划分子序列。
代码（C++）
class Solution
{
public
:
TreeNode
* reConstructBinaryTree(vector
<int> pre
,vector
<int> vin
) {
return BinaryTree(pre
,vin
,0,pre
.size()-1,0,vin
.size()-1);
}
TreeNode
* BinaryTree(vector
<int> pre
,vector
<int> vin
,int p_start
,int p_end
,int i_start
,int i_end
){
if(p_start
>p_end
||i_start
>i_end
) return NULL;
int n
;
for(int i
=i_start
;i
<=i_end
;i
++){
if(pre
[p_start
]==vin
[i
]){
n
=i
;
break;
}
}
TreeNode
* node
=new
TreeNode(vin
[n
]);
node
->left
=BinaryTree(pre
,vin
,p_start
+1,p_start
+n
-i_start
,i_start
,n
-1);
node
->right
=BinaryTree(pre
,vin
,p_start
+n
-i_start
+1,p_end
,n
+1,i_end
);
return node
;
}
};
