Wrong answer, but got the right answer in local testing


  • 0
    H
    /**
     * Definition for binary tree
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
      * }
      */
     public class Solution {
      public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(inorder == null || inorder.length ==0){
            return null;
        }
        
        TreeNode root = new TreeNode(preorder[0]);
        int leftEnd =-1;
        int rightStart =inorder.length;
        int leftInSize = 0;
        
        for(int i=0; i<inorder.length; i++){
            if(inorder[i] == root.val){
                leftEnd = i-1;
                rightStart = i+1;
                break;
            }
        }
        
        if(leftEnd >=0){
            int[] leftIn = new int[leftEnd+1];
            int[] leftPre = new int[leftIn.length];
            System.arraycopy(inorder, 0, leftIn, 0, leftIn.length);
            System.arraycopy(preorder,1,leftPre,0,leftPre.length);
            root.left = buildTree(leftIn, leftPre);
            leftInSize = leftIn.length;
        }
        if(rightStart < inorder.length){
            int[] rightIn = new int[inorder.length - leftInSize -1];
            int[] rightPre = new int[rightIn.length];
            System.arraycopy(inorder, rightStart, rightIn, 0, rightIn.length);
            System.arraycopy(preorder,1+leftInSize,rightPre,0,rightPre.length);
            root.right = buildTree(rightIn, rightPre);
        }
        
        return root;
    }
    }
    

    Wrong Answer:

    Input:	[1,2,3], [3,2,1]
    Output:	{1,3,#,2}
    Expected:	{1,2,#,3}
    

    However, while I'm testing in local, the answer is the same as the expected one.

    root:2left:3
    root:1left:2
    Result:1,2,#,3
    

    I really appreciate any suggestion or solution on this problem!


  • 1
    S

    I'll be very surprised if this piece of code would produce a correct result. Apparently, the way you call buildTree:

    root.left = buildTree(leftIn, leftPre); // Inorder first
    

    is different from how it is defined:

    buildTree(int[] preorder, int[] inorder) // Preorder fist
    

    The version on your computer, should it produce the expected result, must be different from what you provided here.

    BTW, your code can be quite slow and space inefficient. First of all, finding the first element of preorder[] in inorder[] takes O(n) time. You can reduce it to O(1) by making use of a hashmap. Secondly, you may want to try to eliminate copying to new arrays in every recursive call. Instead, you can pass the original arrays around but specify ranges.


  • 0
    H

    Thanks very much for your answer and suggestions.
    What a stupid error! In my computer, I used the opposite arguments sequence, so it got the right answer...


Log in to reply
 

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