# My O(n) Java solution with recursion and Map

• ``````public class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
if (preorder.length == 0 || inorder.length == 0) {
return null;
}

Map<Integer, Integer> orderMap = new HashMap<Integer, Integer>();
for (int i = 0; i < inorder.length; i++) {
orderMap.put(inorder[i], i);
}

return buildTree(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1, orderMap);
}

private TreeNode buildTree(int[] preorder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd, Map<Integer, Integer> orderMap) {
int rootVal = preorder[preStart];
TreeNode root = new TreeNode(rootVal);
if (preStart == preEnd) {
return root;
}

int rootIndx = orderMap.get(rootVal);

int leftNodesCount = rootIndx - inStart;
int rightNodesCount = inEnd - rootIndx;

if (leftNodesCount > 0) {
root.left = buildTree(preorder, preStart + 1, preStart + leftNodesCount,
inorder, inStart, inStart + leftNodesCount - 1, orderMap);
}

if (rightNodesCount > 0) {
root.right = buildTree(preorder, preStart + leftNodesCount + 1, preEnd,
inorder, inStart + leftNodesCount + 1, inEnd, orderMap);
}

return root;
}
}
``````

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