1、思路

在 前缀树 的基础上，往树节点中加入一个val变量代表单词的值，初始值为0。求前缀和时，先遍历单词，对最后一个字母所代表的树节点做dfs，累加其代表的整个子树之值即可。

2、代码

class MapSum {
private:
    struct TrieNode     //前缀树结构体
    {
        int val;        //代表单词的值
        vector<shared_ptr<TrieNode>> children;
        TrieNode() : val(0), children(26, nullptr) {}
    };

    shared_ptr<TrieNode> root = make_shared<TrieNode>();

public:
    MapSum() {

    }

    void insert(string key, int val) {      //单词插入前缀树（构造前缀树）
        auto node = root;
        for (char& ch : key)
        {
            if (node->children[ch - 'a'] == nullptr)
            {
                node->children[ch - 'a'] = make_shared<TrieNode>();
            }

            node = node->children[ch - 'a'];
        }

        node->val = val;                    //更新单词的值
    }

    int dfs(shared_ptr<TrieNode>root)       //累加这个树节点代表的整个子树
    {
        if (root == nullptr) return 0;

        int res = root->val;
        for (auto& child : root->children)
        {
            res += dfs(child);
        }

        return res;
    }

    int sum(string prefix) {        
        auto node = root;
        for (char& ch : prefix)             //遍历单词，找到尾部字母代表的树节点
        {
            if (node->children[ch - 'a'] == nullptr) return 0;
            node = node->children[ch - 'a'];
        }

        return dfs(node);
    }
};