Java日记2018-06-19

7. 重建二叉树

private static HashMap<Integer,Integer> has = new HashMap<>();
    public static TreeNode rebuild(int[] inorder,int[] pre){
        if(inorder==null || pre==null) return null;
        for(int i=0;i<pre.length;i++){
            has.put(pre[i], i);
        }
        return rebuildcore(inorder,0,inorder.length-1,pre,0,pre.length-1);
    }
    public static TreeNode rebuildcore(int[] ino,int ileft,int iright,int[] pre,int pleft,int pright){
        if(pleft>pright) return null;
        TreeNode root = new TreeNode(pre[pleft]);
        int plength = has.get(pre[pleft])-ileft;
        root.left = rebuildcore(ino,ileft,ileft+plength-1,pre,pleft+1,pleft+plength);
        root.right = rebuildcore(ino,ileft+plength,iright,pre,pleft+plength+1,pright);
        return root;
    }

12. 矩阵中的路径