一.解决方法：
在相关的书籍中描述了一个递归的解决方法，其算法思想如下：
1.从前序序列中第一个元素开始，取出一个元素，索引后移一位（preIndex+1）
2.根据选择到的数值创建一个树节点newNode
3.然后查找所选的数值在中序序列中的索引，用inIndex存储
4.递归调用此方法为inIndex之前的数组为中序序列构建一颗子树，将其作为newNode的左子树
5.递归调用此方法为inIndex之后的数组为中序序列构建一颗子树，将其作为newNode的右子树
6.返回newNode
下面我们用实际的例子来推理一遍:
前序遍历{3,9,20,15,7}
中序遍历{9,3,15,20,7}
我们有：
二.代码实现
在代码实现的过程中我们要注意的点是：
1.当前序数组和中序数组都为空时，我们应该返回null
2.当中序数组只有一位时，该节点的左右孩子都为null
下面是代码实现，注释详细，内含测试方法：
public class ChongJianErChaShu { public static void main(String[] args) { ChongJianErChaShu test=new ChongJianErChaShu(); int[] a={1,2}; int[] b={1,2}; TreeNode first=test.buildTree(a,b); test.Check1(first); } void Check1(TreeNode first)//前序遍历 { if(first!=null) { System.out.print(first.val); Check1(first.left); Check1((first.right)); } } /* 重建二叉树 */ int preIndex=0;//全局变量，初始化前序索引 public TreeNode buildTree(int[] preorder, int[] inorder) { //首先检查两个序列的长度，如果一个为零，则返回null if (preorder.length==0||inorder.length==0) { return null; } //然后以前序序列的preIndex索引上的数新建一个节点 TreeNode newNode=new TreeNode(preorder[preIndex]); int inIndex=-1;//初始化中序序列索引 //找到前序数值和中序数值相同的索引赋给inIndex for(int i=0;i<inorder.length;i++) { if(inorder[i]==preorder[preIndex]) { inIndex = i; break; } } preIndex++;//前序索引后移一位 //如果中序索引的第一位就是前序索引的数值且中序子序列只有一个，则说明该节点孩子节点都为null if(inIndex==0&&inorder.length==1) { newNode.left=null; newNode.right=null; return newNode; } //创建左子树序列数组并将该数值前面的数赋给新数组 int[] behindInorder=new int[inIndex]; for(int i=0;i<inIndex;i++) { behindInorder[i]=inorder[i]; } //创建右子树序列数组并将该数值前面的数赋给新数组 int[] afterInorder=new int[inorder.length-1-inIndex]; for(int i=0;i<inorder.length-1-inIndex;i++) { afterInorder[i]=inorder[inIndex+1+i]; } //递归调用创建 newNode.left=buildTree(preorder,behindInorder); newNode.right=buildTree(preorder,afterInorder); return newNode; }} class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } } 77129394
