public TreeNode buildTree(int[] inorder, int[] postorder) {
return build(inorder,inorder.length1,0,postorder,postorder.length1);
}
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,postStart1);
root.left = build(inorder,index1,inEnd,postorder,postStart(inStartindex)1);
return root;
}
My JAVA recursive answer, BEAT 92.9%, 2ms


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.length1,0,postorder,postorder.length1); } 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,postStart1); root.left = build(inorder,i1,inEnd,postorder,postStart(inStarti)1); return root; } }

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 ~12ms. 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.