LeetCode 键值映射题解题目描述设计一个 map支持插入键值对和返回以给定前缀开头的所有键对应的值的总和。示例map new TrieMap(); map.insert(apple, 3); map.sum(ap); // 返回 5解题思路方法字典树思路在字典树的每个节点中维护一个值总和。插入时增加路径上所有节点的值总和。查询时返回对应节点的值总和。复杂度分析时间复杂度O(L)L 是字符串长度。空间复杂度O(L)。代码实现class TrieNode: def __init__(self): self.children {} self.value 0 self.sum 0 class TrieMap: def __init__(self): self.root TrieNode() def insert(self, key, val): node self.root for char in key: if char not in node.children: node.children[char] TrieNode() node node.children[char] node.sum val node.value val def sum(self, prefix): node self.root for char in prefix: if char not in node.children: return 0 node node.children[char] return node.sum # 测试 def test_trie_map(): map TrieMap() map.insert(apple, 3) print(map.sum(ap)) # 输出3 if __name__ __main__: test_trie_map()总结字典树可以维护前缀值总和通过在每个节点存储值总和实现高效的前缀求和查询。