public TreeNode buildTreePostIn(int[] inorder, int[] postorder) {

	if (inorder == null || postorder == null || inorder.length != postorder.length)

		return null;

	HashMap<Integer, Integer> hm = new HashMap<Integer,Integer>();

	for (int i=0;i<inorder.length;++i)

		hm.put(inorder[i], i);

	return buildTreePostIn(inorder, 0, inorder.length-1, postorder, 0,

                          postorder.length-1,hm);

}

private TreeNode buildTreePostIn(int[] inorder, int is, int ie, int[] postorder, int ps, int pe,

                                 HashMap<Integer,Integer> hm){

	if (ps>pe || is>ie) return null;

	TreeNode root = new TreeNode(postorder[pe]);

	int ri = hm.get(postorder[pe]);

	TreeNode leftchild = buildTreePostIn(inorder, is, ri-1, postorder, ps, ps+ri-is-1, hm);

	TreeNode rightchild = buildTreePostIn(inorder,ri+1, ie, postorder, ps+ri-is, pe-1, hm);

	root.left = leftchild;

	root.right = rightchild;

	return root;

}　　

class TreeNode:

    def __init__(self, x):

        self.val = x

        self.left = None

        self.right = None

class Solution:

    # @param inorder, a list of integers

    # @param postorder, a list of integers

    # @return a tree node

    def buildTree(self, inorder, postorder):

        lookup = {}

        for i, num in enumerate(inorder):

            lookup[num] = i

        return self.buildTreeRecu(lookup, postorder, inorder, len(postorder), 0, len(inorder))

    def buildTreeRecu(self, lookup, postorder, inorder, post_end, in_start, in_end):

        if in_start == in_end:

            return None

        node = TreeNode(postorder[post_end - 1])

        i = lookup[postorder[post_end - 1]]

        node.left = self.buildTreeRecu(lookup, postorder, inorder, post_end - 1 - (in_end - i - 1), in_start, i)

        node.right = self.buildTreeRecu(lookup, postorder, inorder, post_end - 1, i + 1, in_end)

        return node

if __name__ ==  "__main__":

    inorder = [2, 1, 3]

    postorder = [2, 3, 1]

    result = Solution().buildTree(inorder, postorder)

    print(result.val)

    print(result.left.val)

    print(result.right.val)

// Time:  O(n)

// Space: O(n)

/**

 * Definition for a binary tree node.

 * struct TreeNode {

 *     int val;

 *     TreeNode *left;

 *     TreeNode *right;

 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}

 * };

 */

class Solution {

public:

    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {

        unordered_map<int, size_t> in_entry_idx_map;

        for (size_t i = 0; i < inorder.size(); ++i) {

            in_entry_idx_map.emplace(inorder[i], i);

        }

        return ReconstructPreInOrdersHelper(preorder, 0, preorder.size(), inorder, 0, inorder.size(),

                                            in_entry_idx_map);

    }

    // Reconstructs the binary tree from pre[pre_s : pre_e - 1] and

    // in[in_s : in_e - 1].

    TreeNode *ReconstructPreInOrdersHelper(const vector<int>& preorder, size_t pre_s, size_t pre_e,

                                           const vector<int>& inorder, size_t in_s, size_t in_e,

                                           const unordered_map<int, size_t>& in_entry_idx_map) {

        if (pre_s == pre_e || in_s == in_e) {

            return nullptr;

        }

        auto idx = in_entry_idx_map.at(preorder[pre_s]);

        auto left_tree_size = idx - in_s;

        auto node = new TreeNode(preorder[pre_s]);

        node->left = ReconstructPreInOrdersHelper(preorder, pre_s + 1, pre_s + 1 + left_tree_size,

                                                  inorder, in_s, idx, in_entry_idx_map);

        node->right = ReconstructPreInOrdersHelper(preorder, pre_s + 1 + left_tree_size, pre_e,

                                                   inorder, idx + 1, in_e, in_entry_idx_map);

        return node;

    }

};