面试题7:重建二叉树

    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        if(pre.length==0||in.length==0) return null;
        TreeNode root = new TreeNode(pre[0]);
        int ind = findInd(pre,in,pre[0]);
        return reConstructBinaryTree(pre,0,pre.length-1,in,0,in.length-1);
    }
    //递归构建树
    //pre数组的pb开始节点是当前的树根
    private static TreeNode reConstructBinaryTree(int[] pre,int pb,int pe,int[] in,int ib, int ie){
        if(pb>pe)
            return null;
        TreeNode head = new TreeNode(pre[pb]);
        // ind 确定树根在中序数组中的位置
            int ind = findInd(pre,in,pre[pb]);
        // 中序数组中，ind左边是当前根的左子树
        //左子树的位置是in[ib,ind-1],包含的节点个数是ind-ib
        // pre[pb]是当前的根，右边是他的子树，左子树从右边第一个起
        //在前序数组中，左子树的位置是pre[pb+1,pb+ind-ib]
            head.left = reConstructBinaryTree(pre,pb+1,ind-ib+pb,in,ib,ind-1);
            head.right = reConstructBinaryTree(pre,ind-ib+pb+1,pe,in,ind+1,ie);
        
        return head;
        
    }
    // val是pre中的值，返回val在in中的位置
    private static int findInd(int[] pre,int[] in,int val){
         for(int i=0;i<in.length;i++){
             if(in[i]==val)
                 return i;
         }
        return -1;
    }