[LeetCode OJ]- Construct Binary

题目要求：给定一颗二叉树的中序遍历的数组inorder[]和前序遍历的数组preorder[]，构造出这颗二叉树。

我们知道，根据前序+中序 或者 后序+中序都可以构造出一颗二叉树，而前序+后序则不能构造出一颗二叉树。

例如，下图的二叉树的

前序序列为：1-3-5-6

中序序列为：3-1-6-5

后序序列为：3-6-5-1

一颗二叉树

那么为什么前序+中序或者后序+中序行，而前序+后序不行呢？

（1）前序+中序的构造过程：

前序序列为：1-3-5-6

中序序列为：3-1-6-5

前序序列是先根，再左，再右的过程。那么前序中的第一个数1一定为二叉树的根，根据这个1我们可以去中序序列中找1所在的位置，然后因为中序序列是先左再根再右的过程，那么中序序列的1的左边部分（3）一定是左子树的节点，1的右边部分（6和5）一定是右子树的节点，根据这个结果，我们再去前序序列中找根的左子树部分……我们发现这是个递归的过程。

第一次递归 第三次递归

直到当前子树的根节点没有左右节点为止，这样，一颗二叉树一定可以被构造出来。

根据这个过程，我们得到了这道题目的解题思路。

需要四个辅助的指针，一个prestart指向当前先序序列中的开始位置（当前树的根节点），一个instart指向当前中序序列的开始位置，一个inend指向当前中序序列的结束位置，一个inIndex指向当前中序序列中的根的位置。

代码如下。

返回结果为