# My JAVA recursive answer, BEAT 92.9%, 2ms

• ``````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;
}``````

• 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;
}
}
``````

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

• 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.

• This post is deleted!

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