剑指offer 7 重建二叉树
递归法：
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
import java.util.HashMap;
public class Solution {
public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
int prelen=pre.length;
int inlen=in.length;
HashMap<Integer, Integer> map = new HashMap<>(inlen);
if(prelen !=inlen){
throw new RuntimeException("wrong input");
}
for(int i=0;i<inlen;i++){
map.put(in[i],i);
}
return reConstructBinaryTree(pre,map,0,prelen-1,0,inlen-1);
}
public TreeNode reConstructBinaryTree(int []pre, HashMap <Integer, Integer>map,int preleft,
int preright,int inleft,int inright){
if(preleft>preright || inleft>inright){
return null;
}
int rootVal=pre[preleft];
TreeNode root=new TreeNode(rootVal);
int pIndex=map.get(rootVal);
root.left=reConstructBinaryTree(pre,map,preleft+1,pIndex-inleft+preleft,inleft,pIndex-1);
root.right=reConstructBinaryTree(pre,map,pIndex-inleft+preleft+1,preright,pIndex+1,inright);
return root;
}
} 