# My java Solution with O(n)

• ``````/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public TreeNode buildTree(int[] inorder, int[] postorder) {
// sanity check
if (inorder == null || postorder == null || inorder.length != postorder.length || inorder.length == 0) {
return null;
}
Map<Integer, Integer> map = getMap(inorder);

return helper(inorder, 0, inorder.length - 1, postorder, 0, postorder.length - 1, map);
}

private TreeNode helper(int[] in, int inl, int inr, int[] post, int postl, int postr, Map<Integer, Integer> map) {
// base case
if (postl > postr) {
return null;
}

//recursive rule
TreeNode root = new TreeNode(post[postr]);
int size = map.get(post[postr]) - inl;
root.left = helper(in, inl, inl + size - 1, post, postl, postl + size - 1, map);
root.right = helper(in, inl + size + 1, inr, post, postl + size, postr - 1, map);
return root;
}

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

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