Intuition for the efficient O(n) recursion
Starting from this video, I would like to explain how the efficient solution works.\n\n\nSuppose we have this tree \n\nIt\'s traversals are as follows \n\nNow, 
Starting from this video, I would like to explain how the efficient solution works.\n<iframe width="560" height="315" src="https://www.youtube.com/embed/IVlCn-DNO5k" frameborder="0" allow="accelerometer; autoplay; encrypted-media; gyroscope; picture-in-picture" allowfullscreen></iframe>\n\nSuppose we have this tree ![image](https://assets.leetcode.com/users/valdrinit/image_1576567347.png)\n\nIt\'s traversals are as follows ![image](https://assets.leetcode.com/users/valdrinit/image_1576567393.png)\n\nNow, it\'s obvious that the last node of the postorder traversal `(A)` will be the root of the tree. As stated in the video, all the nodes from the inorder traversal that are to the left of the root belong to the left subtree `(D,B,F,E)` and all the others belong to the right one `(G,C,L,J,H,K)`. \n\nFrom this, it seems that we need an efficient way of answering the question "given a node in the postorder traversal, where is it at in the inorder array (or what is its index in the inorder traversal)?" This is what the `inorderLocator` map does: it maps each node\'s value to its index in the inorder array `(inorderLocator[node value] = inorder index)`. \n\nWe\'ve seen that dividing the inorder traversal into a left subtree traversal and a right subtree traversal is easy, we just find the root\'s index and split there. But what about dividing the postorder traversal?\n\nThink about how postorder works. **We visit the left subtree first**, then the right subtree, and finally the root. What this means is that **the postorder traversal begins with all the elements of the left subtree (1)**; those are the ones we visit first, right? \n\nWe also know the index of the root in the inorder traversal, and that **the number of elements left of the root in an inorder traversal is exactly the number of elements in the left subtree (2)**. That number happens to be the **index of the root in the traversal minus the index of the first element considered (initially 0)**.\n\nGiven **1** and **2**, we can now divide the postorder traversal into subproblems too. The postorder traversal of the left subtree will have all the elements from `beginning` to `beginning + #(elements in the left subtree) - 1` and the right subtree will have all elements from `beginning + #(elements in the left subtree)` to `ending - 1` (as the last index was the root itself).\n\nIn our example, `A` is at index 4, we have `4 - 0 = 4` elements in the left subtree, so we split the postorder from index `0` to `4 - 1 = 3` `(D,F,E,B)`, and then again from `4` to `10 - 1 = 9` `(G,L,J,K,H,C)`.\n\nWe now have a beautiful recursion: we can solve `f([D,F,E,B,G,L,J,K,H,C,A], [D,B,F,E,A,G,C,L,J,H,K])` by choosing `root = A` and solving `root.left = f([D,F,E,B] [D,B,F,E])` AND `root.right = f([G,L,J,K,H,C], [G,C,L,J,H,K])`. The basecase would be when we want to solve `f([], [])`, and its result would be the null tree.\n\nFor optimization purposes, we could also consider `f([X], [X])` to be a base case, the tree with root X and no children. Also, we won\'t split the arrays, but rather store their boundaries as `[start, end]` indeces so that we only consider the portions from `array[start]` to `array[end]`.\n\n```java\nclass Solution {\n    public Map<Integer, Integer> inorderLocator;\n    \n    public TreeNode buildTree(int[] inorder, int[] postorder) {\n        inorderLocator = new HashMap<>();\n        for (int i = 0; i < inorder.length; i++) {\n            inorderLocator.put(inorder[i], i);\n        }\n        \n        return buildTreeHelper(inorder, 0, inorder.length - 1, postorder, 0, postorder.length - 1);\n    }\n    \n    public TreeNode buildTreeHelper(int[] inorder, int inorderStart, int inorderEnd, int[] postorder, int postorderStart, int postorderEnd) {\n        if (inorderStart > inorderEnd)\n            return null;\n        \n        TreeNode root = new TreeNode(postorder[postorderEnd]);\n\t\tif (inorderStart == inorderEnd)\n\t\t\treturn root;\n        \n        int inorderIndex = inorderLocator.get(postorder[postorderEnd]);\n\t\tint leftSubtreeCount = inorderIndex - inorderStart;\n\t\t\n        root.left = buildTreeHelper(inorder, inorderStart, inorderIndex - 1, postorder, postorderStart, postorderStart + leftSubtreeCount - 1);\n        root.right = buildTreeHelper(inorder, inorderIndex + 1, inorderEnd, postorder, postorderStart + leftSubtreeCount, postorderEnd - 1);\n        \n        return root;\n    }\n}\n```
[]