题目链接：105. 从前序与中序遍历序列构造二叉树 - 力扣（LeetCode）
题目描述：
思路分析：
这道题和昨天写的根据中序遍历和后序遍历构造二叉树（题目链接）的题目思路一样，接下来我们再分析一遍。题目中只给出了两个提示：二叉树前序遍历结果和中序遍历结果，首先我们先分析一下前序遍历结果。
如上图所示，我们发现 ①号就是前序遍历结果的第一个数据，同时它也是二叉树的根节点，②号是前序遍历结果的第二个数据，同时它还是根节点的左子树，接下来我们再看 ③号，③号在前序遍历结果中在②号的后面，而且是根节点的右子树，③号后面还有两个数据，我们按照上述进行标记后得出一个结论：前序遍历的第一个数据就是二叉树的根节点，紧跟在根节点之后的数据就是根节点的左子树，最后一个左子树的数据后面的数据就是根节点的右子树，在这个过程中，顺序一直都是先根节点，再左子树，最后右子树，永远不会改变。
接下来我们再分析一下中序遍历的规律。
根据上图可以发现，在中序遍历的结果中，在根节点左侧的数据恰好是整颗二叉树的左子树，在根节点右侧的数据恰好是整颗二叉树的右子树，接下来我们再分析一下右子树里面的数据，通过观察可以发现，在右子树的根节点左侧的数据是右子树的左子树，在右子树的根节点右侧的数据则是右子树的右子树，与整颗二叉树的分布规律相同。通过分析中序遍历与二叉树的联系，得出结论：根节点位置左侧的数据就是根节点的左子树，根节点位置右侧的数据就是根节点的右子树。
接下来我们分析一下写代码的步骤：
1、在前序遍历中找到根节点，创建根节点 root
2、在中序遍历中找到根节点的位置 rootIndex，然后根据根节点的位置将中序遍历数组分为左子树部分和右子树部分，也就是beg（begin）~rootIndex-1 和 rootIdex+1 ~ end 两部分
3、构造左子树和右子树，顺序必须是先左子树再右子树，然后重复此过程，直到完全构造出二叉树
代码示例：
class Solution {
public int index = 0;
public TreeNode buildTree(int[] preorder, int[] inorder) {
int len = preorder.length-1;
// 构造树
return createTree(preorder,inorder,0,inorder.length-1,len);
}
public TreeNode createTree(int[] preorder,int[] inorder,int beg,int end,int len) {
if(beg > end) return null;
TreeNode root = new TreeNode(preorder[index]);
// 在中序遍历中找到 root 的位置
int rootIndex = findIndex(inorder,preorder[index],beg,end);
index++;
// 构建左子树和右子树
root.left = createTree(preorder,inorder,beg,rootIndex-1,len);
root.right = createTree(preorder,inorder,rootIndex+1,end,len);
return root;
}
public int findIndex(int[] inorder,int val,int beg, int end) {
for(int i = beg; i <= end; i++) {
if(inorder[i] == val) return i;
}
return -1;
}
}