剑指offer_7_重建二叉树

Map<Integer,Integer> map = new HashMap<>();

public TreeNode fill(int[] pre,int[] in) {
    for (int i = 0; i < in.length; i++) {
        map.put(in[i],i);
    }
    return reBuild(pre,0,pre.length -1,0);
}
    // pre[] 前序遍历 preL：当前前序遍历数组的最左侧 preR：当前前序遍历数组的最右侧 inL中序遍历的最左侧
public TreeNode reBuild(int[] pre,int preL,int preR,int inL) {
     if (preL > preR) {
         return null;
     }
    TreeNode root = new TreeNode(pre[preL]);
     // 得到该节点的下标
     int inIndex = map.get(root.value);
     // 左子树的大小
     int lTreeSize = inIndex - inL;
     // 递归左边的子树
     root.left = reBuild(pre,preL + 1,preL + lTreeSize,inL);
     // 递归右边的子树 inL + lTreeSize + 1:当前中序遍历数组的最左侧元素
     root.right = reBuild(pre,preL + lTreeSize + 1,preR,inL + lTreeSize + 1);
    return root;
 }
}

class TreeNode {
    TreeNode left;
    TreeNode right;
    int value;
    public TreeNode(int value) {
        this.value = value;
    }
}