题解 | #重建二叉树#

public static TreeNode reConstructBinaryTree(int [] pre,int [] vin) {
if (pre==null||vin==null||pre.length!= vin.length||pre.length<=0){
return null;
}
return ConstructTree(pre,0, pre.length-1, vin,0, vin.length-1);
}
public static TreeNode ConstructTree(int [] pre,int start1,int end1,int [] vin ,int
start2,int end2){
TreeNode root = new TreeNode(pre[start1]);

if (start1==end1){
    if(start2==end2&&pre[start1]==vin[start2]){
      return root;   
    }

}
int tempLeft = start2;
for (int i = start2; i <=end2 ; i++) {
  if (pre[start1]==vin[i]){
    tempLeft= i;
    break;
  }
}
int left = tempLeft - start2;
int leftEnd = start1+left;
if (left>0){
  root.left  = ConstructTree(pre,start1+1,leftEnd,vin,start2,tempLeft-1);
}
  int right = end2-tempLeft;
if (right>0){
  root.right  = ConstructTree(pre,leftEnd+1,end1,vin,tempLeft+1,end2);
}
return root;
}