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

``````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!

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