106. Construct Binary Tree from Inorder and Postorder Traversal - cocoder39/coco39_LC GitHub Wiki

class Solution {
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        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);
    }
private:
    TreeNode* helper(vector<int>& inorder, int in_sta, int in_end, vector<int>& postorder, int pos_sta, int pos_end, unordered_map<int, int>& map) {
        if (in_sta > in_end || pos_sta > pos_end) {
            return nullptr;
        }
        
        int in_root = map[postorder[pos_end]];
        int pos_sta_left = pos_sta;
        int pos_end_left = pos_sta_left + (in_root - 1 - in_sta);
        int pos_sta_right = pos_end_left + 1;
        int pos_end_right = pos_end - 1;
        
        TreeNode* root = new TreeNode(postorder[pos_end]);
        root->left = helper(inorder, in_sta, in_root - 1, postorder, pos_sta_left, pos_end_left, map);
        root->right = helper(inorder, in_root + 1, in_end, postorder, pos_sta_right, pos_end_right, map);
        return root;
    }
};