[Java] 1ms, beats 100%, no map, clean recursion
105 is same as 106 (almost) here are the comparisons, check the similarity and differences\n# 105 inorder + preorder\nwe use preorder to create nodes from left 
105 is same as 106 (almost) here are the comparisons, check the similarity and differences\n# [105 inorder + preorder](https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/)\nwe use preorder to create nodes from left to right, whenever we go left, we need to pass current root value as right boundary for it\'s whole left sub tree(root has no boundary, so used 3001 as valid nodes are from 1-3000, you could use Integer.MAX_VALUE), so that the left sub tree creation will know when to exit to go right subtree, the right bounary of right subtree is right subtree\'s parent\'s parent which was passed in.\n```java\nclass Solution { // TC: O(n), SC: O(height)\n   int i, p; // i as index for inorder, p as index for preorder\n   public TreeNode buildTree(int[] pre, int[] in) {\n      i = p = 0;\n      return dfs(pre, in, 3001);\n   }\n\n   private TreeNode dfs(int[] pre, int[] in, int rightBoundary) {\n      if (p == pre.length || in[i] == rightBoundary) return null;\n\n      TreeNode node = new TreeNode(pre[p++]);\n      node.left  = dfs(pre, in, node.val);\n      i++;\n      node.right = dfs(pre, in, rightBoundary);\n      return node;\n   }\n}\n```\n# [106 inorder + postorder](https://leetcode.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/)\nAlmost exactly same as above, but we go backwards and create right sub tree first (and check for left boundary as end because we scan backwards right to left)\n```java\nclass Solution {\n    int i, o; // i: inorder traversal idx, o: postorder traversal idx;\n    public TreeNode buildTree(int[] in, int[] po) {\n        i = o = po.length - 1;\n        return dfs(in, po, 3001);\n    }\n    \n    private TreeNode dfs(int[] in, int[] po, int leftBoundary) {\n        if (o == -1 || in[i] == leftBoundary) return null;\n        TreeNode node = new TreeNode(po[o--]);\n        node.right = dfs(in, po, node.val);\n        i--;\n        node.left  = dfs(in, po, leftBoundary);\n        return node;\n    }\n}\n```\n
['Recursion', 'Java']