5ms Java Clean Solution with Caching


  • 27

    In this questions, most of people just loop through inorder[] to find the root. However, by caching positions of inorder[] indices using a HashMap, the run time can drop from 20ms to 5ms.

    Here is my 5ms AC solution:

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        Map<Integer, Integer> inMap = new HashMap<Integer, Integer>();
        
        for(int i = 0; i < inorder.length; i++) {
            inMap.put(inorder[i], i);
        }
    
        TreeNode root = buildTree(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1, inMap);
        return root;
    }
    
    public TreeNode buildTree(int[] preorder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd, Map<Integer, Integer> inMap) {
        if(preStart > preEnd || inStart > inEnd) return null;
        
        TreeNode root = new TreeNode(preorder[preStart]);
        int inRoot = inMap.get(root.val);
        int numsLeft = inRoot - inStart;
        
        root.left = buildTree(preorder, preStart + 1, preStart + numsLeft, inorder, inStart, inRoot - 1, inMap);
        root.right = buildTree(preorder, preStart + numsLeft + 1, preEnd, inorder, inRoot + 1, inEnd, inMap);
        
        return root;
    }

  • 1
    N

    Same idea with me.

    But i found that HashMap is a bit "slow" for this problem.I tried to replace it with array, and it did work faster.
    Here is my implementation.

    //after a few trial and error, i found out that all data are in range(-4000,4000)
    //so i assumed that there would be 8000 different numbers at most
    private static final int[]nodeMap = new int[8192];
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        TreeNode root = null;
        if(preorder.length>0){
            for(int i=0;i<inorder.length;i++){
                nodeMap[inorder[i]+4096] = i;
            }
            root = buildTree(preorder,0,preorder.length-1,nodeMap,0,inorder.length-1);
        }
        return root;
    }
    private TreeNode buildTree(int[] preorder, int ps,int pe,int[]inOrderMap,int is,int ie){
        int nodeVal = preorder[ps];
        TreeNode root = new TreeNode(nodeVal);
        int inorderIdx = inOrderMap[nodeVal+4096];
        int leftSize = inorderIdx-is;
        int rightSize = ie-inorderIdx;
        if(leftSize>0){
            root.left = buildTree(preorder,ps+1,ps+leftSize-1,inOrderMap,is,inorderIdx-1);
        }
        if(rightSize>0){
            root.right = buildTree(preorder,ps+leftSize+1,pe,inOrderMap,inorderIdx+1,ie);
        }
        return root;
    }
    

  • 3

    Dear @newdive, thanks so much for the nice solution. However, what if we add another test case, say Integer.MIN_VALUE? We cannot assume it's within (-4000,4000) by hacking the test cases, right?


  • 0
    2

    You make use of the O(1) lookup time of hashtable, and make the algorithm to linear time. Great!


  • 0
    J

    @newdive This solution beats 98% thanks.


  • 0
    R

    I use the HashMap too, but why my solutiong usinng 120ms to slove the problem, which just beats 0.83% .

    public class Solution {
        public TreeNode buildTree(int[] preorder, int[] inorder) {
            if(preorder==null||inorder==null||preorder.length==0||inorder.length==0) return null;
            Map<Integer,Integer> inorderMap=new HasMap(inorder.length);
            for(int i=0;i<inorder.length;i++){
                inorder.put(inorder[i],i);
            }
            TreeNode root=new TreeNode(preorder[0]);
            for(int i=1;i<preorder.length;i++){
                int node=inorderMap.get(preorder[i])
                TreeNode tmp=root;
                while(true){
                    int povit=inorderMap.get(tmp.val);
                    if(node<povit){
                        if(tmp.left==null){tmp.left=new TreeNode(preorder[i]); break;}
                        else tmp=tmp.left;
                    }else{
                        if(tmp.right==null){tmp.right=new TreeNode(preorder[i]; break;)}
                        else tmp=tmp.right;
                    }
                }
            }
            return root;
        }
    }

  • 0
    Y

    this should be the best solution.


Log in to reply
 

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