输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
前序序列的第一个结点一定是根节点，然后遍历中序序列找到根结点所在位置，在根结点之前的都是根结点左子树上的结点，在根节点之后的都是根节点右子树上的结点
然后递归调用来构建左右子树
1 public TreeNode reConstructBinaryTree(int [] pre,int [] in) { 2 if(pre==null || in==null) 3 return null; 4 if(pre.length*in.length==0) 5 return null; 6 return buildTree(pre,0,pre.length-1, 7 in,0,in.length-1); 8 } 9 public TreeNode buildTree(int[] a, int ab, int ae, 10 int[] b, int bb, int be){ 11 if(ab>ae || bb>be) 12 return null; 13 TreeNode node = new TreeNode(a[ab]); 14 int bi = -1; 15 for(int i=bb;i<=be;i++){ 16 if(b[i]==a[ab]){ 17 bi = i; 18 break; 19 } 20 } 21 int size = bi-bb-1; 22 node.left = buildTree(a,ab+1,ab+1+size,b,bb,bi-1); 23 node.right = buildTree(a,ab+1+size+1,ae,b,bi+1,be); 24 return node; 25 }
原文：https://www.cnblogs.com/huanglf714/p/11068908.html