My recursive Java code with O(n) time and O(n) space
The the basic idea is to take the last element in postorder array as the root, find the position of the root in the inorder array; then locate the range for lef
The the basic idea is to take the last element in postorder array as the root, find the position of the root in the inorder array; then locate the range for left sub-tree and right sub-tree and do recursion. Use a HashMap to record the index of root in the inorder array.\n\n    public TreeNode buildTreePostIn(int[] inorder, int[] postorder) {\n    \tif (inorder == null || postorder == null || inorder.length != postorder.length)\n    \t\treturn null;\n    \tHashMap<Integer, Integer> hm = new HashMap<Integer,Integer>();\n    \tfor (int i=0;i<inorder.length;++i)\n    \t\thm.put(inorder[i], i);\n    \treturn buildTreePostIn(inorder, 0, inorder.length-1, postorder, 0, \n                              postorder.length-1,hm);\n    }\n    \n    private TreeNode buildTreePostIn(int[] inorder, int is, int ie, int[] postorder, int ps, int pe, \n                                     HashMap<Integer,Integer> hm){\n    \tif (ps>pe || is>ie) return null;\n    \tTreeNode root = new TreeNode(postorder[pe]);\n    \tint ri = hm.get(postorder[pe]);\n    \tTreeNode leftchild = buildTreePostIn(inorder, is, ri-1, postorder, ps, ps+ri-is-1, hm);\n    \tTreeNode rightchild = buildTreePostIn(inorder,ri+1, ie, postorder, ps+ri-is, pe-1, hm);\n    \troot.left = leftchild;\n    \troot.right = rightchild;\n    \treturn root;\n    }
[]