元素的索引的保存--Map

根据根节点在中序遍历的位置去划分左右子树，然后递归，注意，每次会生成一个根节点，所以元素个数需要减一。

元素与索引的关系可以使用map保存，这样就不需要遍历了。

    /**
     * 输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。
     * 假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
     * 例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
     * @param pre 前序遍历
     * @param in 中序遍历
     * @return 二叉树
     */

    HashMap<Integer,Integer> indexInMiddle=new HashMap<>();
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        for(int i=0;i<in.length;i++){
            indexInMiddle.put(in[i],i);
        }
        return reConstructBinaryTreeRecur(0,0,in.length-1,pre);

    }

    public TreeNode reConstructBinaryTreeRecur(int preRoot,int inLeft,int inRight,int[] pre){
        if(inLeft>inRight){
            return null;
        }
        //每次归位一个元素。root。。根据根在中序遍历的位置，划分左右子树，然后递归！！！
        int rootVal=pre[preRoot];
        TreeNode root=new TreeNode(rootVal);
        int rootIndexInMiddle=indexInMiddle.get(rootVal);
        root.left=reConstructBinaryTreeRecur(preRoot+1,inLeft,rootIndexInMiddle-1,pre);
        root.right=reConstructBinaryTreeRecur(preRoot+rootIndexInMiddle-inLeft+1,rootIndexInMiddle+1,inRight,pre);
        return root;
    }

根节点索引+中序遍历左右边界的索引
大佬的图解如下。地址为：https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof/solution/mian-shi-ti-07-zhong-jian-er-cha-shu-di-gui-fa-qin/