My JAVA recursive answer, BEAT 92.9%, 2ms


  • 5
    F
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        return build(inorder,inorder.length-1,0,postorder,postorder.length-1);
    }
    
    public TreeNode build(int[] inorder, int inStart, int inEnd, int[] postorder, int postStart){
    	if(inEnd > inStart){
    		return null;
    	}
    	TreeNode root = new TreeNode(postorder[postStart]);
    	if(inEnd == inStart){
    		return root;
    	}
    	int index = 0;
    	// find the index in inorder:
    	for(int i = inStart; i >= inEnd; i--){
    		if(inorder[i] == root.val){
    			index = i;
    			break;
    		}
    	}
    	
    	root.right = build(inorder,inStart,index+1,postorder,postStart-1);
    	root.left = build(inorder,index-1,inEnd,postorder,postStart-(inStart-index)-1);
    	
    	return root;
    }

  • 1
    G

    I updated your code, remove index, it might be more concise.

    public class Solution {
       public TreeNode buildTree(int[] inorder, int[] postorder) {
        return build(inorder,inorder.length-1,0,postorder,postorder.length-1);
    }
    
    private TreeNode build(int[] inorder, int inStart, int inEnd, int[] postorder, int postStart){
    	if(inEnd > inStart){
    		return null;
    	}
    	TreeNode root = new TreeNode(postorder[postStart]);
    	if(inEnd == inStart){
    		return root;
    	}
    	int i = 0;
    	// find the index in inorder:
    	for(i = inStart; i >= inEnd; i--){
    		if(inorder[i] == root.val){
    			break;
    		}
    	}
    	
    	root.right = build(inorder,inStart,i+1,postorder,postStart-1);
    	root.left = build(inorder,i-1,inEnd,postorder,postStart-(inStart-i)-1);
    	
    	return root;
    }
    }
    

  • 0
    P

    Seems like traversing the inOrder array in the backward direction made the huge difference.


  • 1
    O

    I agree with @piyush121. I wrote a similar code and was traversing forward. It was taking ~20ms every time. By changing to backward traversal it became ~1-2ms. Since the location of the root in the inorder array is uniformly distributed, it seems like the test cases are biased toward left subtrees being larger.

    Edit: Putting all inorder array value into hashmap should have made the algorithm faster, but it actually slows it down to ~5ms. Looks like test cases are really biased.


  • 0
    S
    This post is deleted!

Log in to reply
 

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