# A concise, D&C, within 10 lines, JAVA solution. Any suggestions?

• The basic idea is divide and conquer, and at first I use Arrays.binarySearch() to locate the root index, however, it requies the array to be sorted first, which I cannot do in my program. So I write a arraySearch() methods myself.

1. Find the root first. The root would be the last element of the postorder[].
2. Find the index of root in inorder[].
3. Divide the inorder[] and postorder[] into root.left part and root.right part.
4. Repeat.

I'm a newbee to JAVA, so despite the recursive approach, I think I'm using O(1) space and O(n) time in solving this problem. Am I right?

And if there's any suggestions or advices you may have to my solution, I would be more than happy to take them all!!!

``````   /**
* 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[] inorder, int[] postorder) {
if(inorder==null||postorder==null||inorder.length==0||postorder.length==0||postorder.length!=inorder.length) return null;
int rootVal = postorder[postorder.length-1];
TreeNode root = new TreeNode(rootVal);
int rootIndex = arraySearch(inorder, rootVal);
if(rootIndex>0) root.left = buildTree(Arrays.copyOfRange(inorder, 0,rootIndex), Arrays.copyOfRange(postorder,0,rootIndex));
if(rootIndex<inorder.length-1) root.right = buildTree(Arrays.copyOfRange(inorder, rootIndex+1,inorder.length),Arrays.copyOfRange(postorder,rootIndex,postorder.length-1));
return root;
}

private int arraySearch(int[] A, int target){
for(int i=0;i<A.length;i++){
if(A[i]==target) return i;
}
return -1;
}
}``````

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