# 106-Construct Binary Tree from Inorder and Postorder Traversal

###### tags: `Medium`
Hint:
改成從post-order找最後一個一定是root 再去分左右子樹

*注意左右子樹遞迴時 postl跟postr 和 inl跟inr 表示要正確

class Solution {
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        if(inorder.size() == 0 || postorder.size() == 0) return NULL;      
        unordered_map<int, int> map;
        for(int i = 0; i < inorder.size(); i++){
            map[inorder[i]] = i;
        }
        
        return helper(inorder, 0, inorder.size() - 1, postorder, 0, postorder.size() - 1, map);
    }
    
    TreeNode* helper(vector<int>& inorder, int in_start, int in_end, vector<int>& postorder, int post_start, int post_end, unordered_map<int, int>& map){
        if(in_start > in_end || post_start > post_end) return NULL;
        int root_val = postorder[post_end];
        TreeNode* root = new TreeNode(root_val);
        int index = map[root_val];
        root->left = helper(inorder, in_start, index - 1, postorder, post_start, post_start + index - 1 - in_start, map);
        root->right = helper(inorder, index + 1, in_end, postorder, post_end - in_end + index, post_end - 1, map);
        return root;
    }
};