package com.freetymekiyan.algorithms.level.medium;

/**
 * Given preorder and inorder traversal of a tree, construct the binary tree
 * <p>
 * Note:
 * You may assume that duplicates do not exist in the tree.
 * <p>
 * Tags: Tree, Array, DFS
 */
class ConstructBTPreInOrder {

    public static void main(String[] args) {

    }

    /**
     * Get root in preorder and search root in inorder
     * Then find range for left subtree and right subtree
     * Recurse down to build subtrees and connect to root
     */
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder == null || inorder == null) return null;
        return buildTree(preorder, inorder, 0, preorder.length - 1, 0, inorder.length - 1);
    }

    public TreeNode buildTree(int[] preorder, int[] inorder, int ps, int pe, int is, int ie) {
        if (ps > pe) return null;
        int pos = is;
        TreeNode root = new TreeNode(preorder[ps]);
        for (; pos <= ie; pos++) { // find root in inorder, no duplicates
            if (inorder[pos] == preorder[ps]) break;
        }
        root.left = buildTree(preorder, inorder, ps + 1, ps - is + pos, is, pos - 1); // left subtree
        root.right = buildTree(preorder, inorder, ps - is + pos + 1, pe, pos + 1, ie); // right subtree
        return root;
    }

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }
}

@@ -45,19 +45,200 @@
 edium;%0A%0A
-/**
+import com.freetymekiyan.algorithms.utils.Utils.TreeNode;%0A%0Aimport java.util.HashMap;%0Aimport java.util.Map;%0A%0A/**%0A * 105. Construct Binary Tree from Preorder and Inorder Traversal%0A * %3Cp%3E
 %0A * Give
@@ -455,61 +455,8 @@
  %7B%0A%0A
-    public static void main(String%5B%5D args) %7B%0A%0A    %7D%0A%0A
     
@@ -513,16 +513,17 @@
  inorder
+.
 %0A     * 
@@ -568,24 +568,25 @@
 ight subtree
+.
 %0A     * Recu
@@ -631,16 +631,17 @@
  to root
+.
 %0A     */
@@ -781,25 +781,19 @@
  return 
-buildTree
+dfs
 (preorde
@@ -867,33 +867,246 @@
     
-public TreeNode buildTree
+/**%0A     * @param ps start index of preorder, inclusive%0A     * @param pe end index of preorder, inclusive%0A     * @param is start index of inorder, inclusive%0A     * @param ie end index of inorder, inclusive%0A     */%0A    private TreeNode dfs
 (int
@@ -1313,17 +1313,17 @@
 +) %7B // 
-f
+F
 ind root
@@ -1333,16 +1333,22 @@
  inorder
+ array
 , no dup
@@ -1354,16 +1354,30 @@
 plicates
+. Linear scan.
 %0A       
@@ -1428,24 +1428,64 @@
 ;%0A        %7D%0A
+        // Use pe - ps = ie - is to get%0A
         root
@@ -1488,33 +1488,27 @@
 root.left = 
-buildTree
+dfs
 (preorder, i
@@ -1555,24 +1555,8 @@
  1);
- // left subtree
 %0A   
@@ -1573,25 +1573,19 @@
 right = 
-buildTree
+dfs
 (preorde
@@ -1636,25 +1636,8 @@
 ie);
- // right subtree
 %0A   
@@ -1669,153 +1669,985 @@
     
-public class TreeNode %7B%0A        int val;%0A        TreeNode left;%0A        TreeNode right
+/**%0A     * Optimized.%0A     * Replace linear scan with a map.%0A     * So that the index of root can be returned in O(1).%0A     */%0A    public TreeNode buildTree2(int%5B%5D preorder, int%5B%5D inorder) %7B%0A        if (preorder == null %7C%7C inorder == null) return null;%0A        Map%3CInteger, Integer%3E valToIndex = new HashMap%3C%3E();%0A        for (int i = 0; i %3C inorder.length; i++) %7B%0A            valToIndex.put(inorder%5Bi%5D, i);%0A        %7D%0A        return dfs(preorder, inorder, 0, preorder.length - 1, 0, inorder.length - 1, valToIndex)
 ;%0A
-%0A
     
+%7D%0A%0A
     
-TreeNode(int x) %7B%0A            val = x;%0A        %7D
+private TreeNode dfs(int%5B%5D preorder, int%5B%5D inorder, int ps, int pe, int is, int ie, Map%3CInteger, Integer%3E valToIdx) %7B%0A        if (ps %3E pe) return null;%0A        int rootIdx = valToIdx.get(preorder%5Bps%5D);%0A        TreeNode root = new TreeNode(preorder%5Bps%5D);%0A        root.left = dfs(preorder, inorder, ps + 1, ps - is + rootIdx, is, rootIdx - 1);%0A        root.right = dfs(preorder, inorder, ps - is + rootIdx + 1, pe, rootIdx + 1, ie);%0A        return root;
 %0A   

update 105. Construct Binary Tree from Preorder and Inorder Traversal