假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
public class Solution {
public TreeNode reConstructBinaryTree(int [] pre,int [] in) {TreeNode root=reConstructBinaryTree(pre,0,pre.length-1,in, 0,in.length-1);
return root;
}
public TreeNode reConstructBinaryTree(int[] pre,int prestart,int preend,int[] in,int instart,int inend)
{
if(prestart>preend||instart>inend){
return null;
}
TreeNode root=new TreeNode(pre[prestart]);
for(int i=instart;i<=inend;i++)
{
if(in[i]==root.val){
//构建左子树
root.left=reConstructBinaryTree(pre,prestart+1,prestart+i-instart,in,instart,i-1);
//构建右子树
root.right=reConstructBinaryTree(pre,prestart+i-instart+1,preend,in,i+1,inend);
}
}
return root;
}
}
分析：前序遍历的第一个元素是根元素，在中序数组中找到根元素，不断找到根元素和构造左子树和右子树。