（1）通过前序列表（根左右） 和 中序列表（左跟右）来重建二叉树
思路 前序遍历 序列中，第一个数字总是二叉树的根节点。在中序遍历 序列中，根节点的值在序列的中间，左子树的节点的值位于根节点的值的左边，右子树的节点的值位于根节点的值的右边。根据二叉树的这个性质，采用递归方法可以重建一个二叉树了。
/** * Definition for binary tree * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public TreeNode reConstructBinaryTree(int [] pre,int [] in) { TreeNode node=reConstructBinaryTree(pre,0,pre.length-1,in,0,in.length-1); return node; } public TreeNode reConstructBinaryTree(int [] pre,int ps,int pe,int [] in,int is,int ie) { if(ps>pe)//如果开始位置大于结束位置说明已经处理到叶节点了 return null; int value=pre[ps]; int index=is; while(index<=ie&&in[index]!=value)//找到的index为根节点在中序遍历序列中的索引 index++; TreeNode node=new TreeNode(pre[startPre]); node.left=reConstructBinaryTree(pre,ps+1,ps+index-is,in,is,index-1); node.right=reConstructBinaryTree(pre,ps+index-is+1,pe,in,index+1,ie); return node; } }