So weird! Just changing the searching direction can make 15ms to 1ms! I really don't understand


  • 1

    Blow is the first solution I can give, which takes 15 ms. Looks like a terrible solution.

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return helper(preorder, 0, inorder, 0, inorder.length - 1);
    }
    
    public static TreeNode helper(int[] preorder, int preStart, int[] inorder, int inStart, int inEnd) {
        if (preStart > preorder.length-1 || inStart > inEnd) {
            return null;
        }
        TreeNode root = new TreeNode(preorder[preStart]);
        int index= inStart;
        while (inorder[index] != preorder[preStart]) {
            index++;
        }
        root.left = helper(preorder, preStart + 1, inorder, inStart, index - 1);
        root.right = helper(preorder, preStart + index - inStart + 1, inorder, index + 1, inEnd);
        return root;
    }
    

    Then I checked the discussion other people posted. I found out that many good solutions tend to search from tail to head when searching for the index in inorder[]. So I try it in solution 1 and I get solution 2.
    Here is the change on the base of solution 1:

        int index= inEnd;
        while (inorder[index] != preorder[preStart]) {
            index--;
        }
    

    The running time turned out to be 1ms now! OMG! ! I am so confused because I thought the searching direction doesn't matter at all . Could anyone tell why. Thanks!


  • 0
    A

    @shakeway Indeed this is weird. It shouldn't matter, unless most of the testcases tend to have a lot more leaves on left branches than on right branches.


Log in to reply
 

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