Java solution in O(n)


  • 2
    D

    the idea is to use a HashMap to find elements in O(1)

    public TreeNode buildTree(int[] p, int[] i) {
        HashMap<Integer,Integer>hm=new HashMap<>();
        for(int a=0;a<i.length;a++)hm.put(i[a],a);
        return buildTree(p,i,new Wrapper(0),0,i.length-1,hm);
    }
    public TreeNode buildTree(int[] p, int[] i,Wrapper w,int s,int e,HashMap<Integer,Integer>hm) {
        if(s>e)return null;
        TreeNode root=new TreeNode(p[w.a++]);
        int idx=hm.get(root.val);
        root.left=buildTree(p,i,w,s,idx-1,hm);
        root.right=buildTree(p,i,w,idx+1,e,hm);
        return root;
    }
    
    class Wrapper{
        int a;
        Wrapper(int _a){
            a=_a;
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.