/**
 * 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[] preorder, int[] inorder) {
    return tree(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
  }

  private TreeNode tree(int[] preorder, int pi, int pj, int[] inorder, int ii, int ij) {
    if (pi > pj) return null;
    TreeNode root = new TreeNode(preorder[pi]);
    int rootIndex = -1;
    for (int k = ii; k <= ij; k++) {
      if (preorder[pi] == inorder[k]) {
        rootIndex = k;
        break;
      }
    }
    root.left = tree(preorder, pi + 1, pi + (rootIndex - ii), inorder, ii, rootIndex - 1);
    root.right = tree(preorder, pi + (rootIndex - ii) + 1, pj, inorder, rootIndex + 1, ij);
    return root;
  }
}

@@ -1,8 +1,341 @@
+// Fairly naive solution where at each level we search inorder array to find the partition index.%0A// This results in O(n%5E2) time in worst case and O(n) space complexity, because you will have to%0A// recursively scan N elements when tree is skewed on one side (in particularly,%0A// when %5B1, 2, 3, 4%5D inorder and %5B4, 3, 2, 1%5D preorder)%0A%0A
 /**%0A * D
@@ -501,23 +501,16 @@
 * %7D%0A */%0A
-public 
 class So
@@ -575,24 +575,80 @@
  inorder) %7B%0A
+    if (preorder.length != inorder.length) return null;%0A
     return t
@@ -771,17 +771,15 @@
 int 
-p
 i, int 
-p
 j, i
@@ -800,18 +800,16 @@
 int 
-ii
+p
 , int 
-ij
+q
 ) %7B%0A
@@ -820,15 +820,22 @@
 if (
-p
 i %3E 
-p
 j
+ %7C%7C p %3E q
 ) re
@@ -887,17 +887,16 @@
 reorder%5B
-p
 i%5D);%0A   
@@ -904,94 +904,636 @@
 int 
-rootIndex = -1;%0A    for (int k = ii; k %3C= ij; k++) %7B%0A      if (preorder%5Bpi%5D ==
+k = p;%0A    while (k %3C= q) %7B%0A      if (inorder%5Bk%5D == preorder%5Bi%5D) break;%0A      k++;%0A    %7D%0A    root.left = tree(preorder, i + 1, i + k - p, inorder, p, k - 1);%0A    root.right = tree(preorder, i + k - p + 1, j, inorder, k + 1, q);%0A    return root;%0A  %7D%0A%7D%0A%0A// Improved solution where we use HashMap to locate partition index.%0A// This runs in O(n) time and has O(n) space complexity.%0A%0A/**%0A * Definition for a binary tree node.%0A * public class TreeNode %7B%0A *     int val;%0A *     TreeNode left;%0A *     TreeNode right;%0A *     TreeNode(int x) %7B val = x; %7D%0A * %7D%0A */%0Aclass Solution %7B%0A  public TreeNode buildTree(int%5B%5D preorder, int%5B%5D
  inorder
 %5Bk%5D)
@@ -1532,19 +1532,16 @@
 rder
-%5Bk%5D
 ) %7B%0A    
     
@@ -1540,144 +1540,595 @@
     
-    rootIndex = k;%0A        break;%0A      %7D%0A    %7D%0A    root.left = tree(preorder, pi + 1, pi + (rootIndex - ii), inorder, ii, rootIndex - 1
+if (preorder.length != inorder.length) return null;%0A    HashMap%3CInteger, Integer%3E in = new HashMap%3CInteger, Integer%3E();%0A    for (int i = 0; i %3C inorder.length; i++) %7B%0A      in.put(inorder%5Bi%5D, i);%0A    %7D%0A    return tree(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1, in);%0A  %7D%0A%0A  private TreeNode tree(int%5B%5D preorder, int i, int j, int%5B%5D inorder, int p, int q, HashMap%3CInteger, Integer%3E in) %7B%0A    if (i %3E j) return null;%0A    TreeNode root = new TreeNode(preorder%5Bi%5D);%0A    int k = in.get(preorder%5Bi%5D);%0A    root.left = tree(preorder, i + 1, i + k - p, inorder, p, k - 1, in
 );%0A 
@@ -2162,36 +2162,23 @@
 er, 
-p
 i + 
-(rootIndex - ii)
+k - p
  + 1, 
-p
 j, i
@@ -2189,25 +2189,20 @@
 er, 
-rootIndex
+k
  + 1, 
-ij
+q, in
 );%0A 

add solution