根据一棵树的前序遍历与中序遍历构造二叉树。
注意:
你可以假设树中没有重复的元素。
例如，给出
前序遍历 preorder = [3,9,20,15,7]中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树：
3/ \9 20/ \15 7
1.先回顾前序遍历和中序遍历的框架：
void traverse(TreeNode root) {// 前序遍历preorder.add(root.val);traverse(root.left);traverse(root.right);}void traverse(TreeNode root) {traverse(root.left);// 中序遍历inorder.add(root.val);traverse(root.right);}
通过上面的图观察规律，前序遍历第一个值肯定是根结点，中序遍历，根结点左边都是左子树，右边都是右子树
对于preorder数组呢？如何确定左右数组对应的起始索引和终止索引？
这个可以通过左子树的节点数推导出来，假设左子树的节点数为leftSize，那么preorder数组上的索引情况是这样的：
class Solution {public TreeNode buildTree(int[] preorder, int[] inorder) {return helpBuild(preorder,0,preorder.length-1,inorder,0,inorder.length-1);}private TreeNode helpBuild(int[] preorder,int preStart,int preEnd,int[] inorder,int inorderStart,int inordorEnd){if(preStart>preEnd){return null;}int rootVal = preorder[preStart];TreeNode root = new TreeNode(rootVal);int index = 0;for(int i=0;i<=inordorEnd;i++){if(rootVal == inorder[i]){index = i;break;}}int leftSize = index - inorderStart;root.left = helpBuild(preorder,preStart+1,preStart+leftSize,inorder,inorderStart,index-1);root.right = helpBuild(preorder,preStart+leftSize+1,preEnd,inorder,index+1,inordorEnd);return root;}}
如果觉得《leetcode刷题（97）——105. 从前序与中序遍历序列构造二叉树》对你有帮助，请点赞、收藏，并留下你的观点哦！
