中进阶

Trie树#

一句话答案#

Trie（前缀树）每条边代表一个字符，从根到节点的路径表示前缀，操作 O(m)，适合前缀搜索和自动补全。

核心要点

结构： children[26] 数组 + isEnd 标记

应用： 搜索自动补全 / 拼写检查 / IP最长前缀匹配

面试回答（2分钟版）

Trie树也叫前缀树，它的核心思想是用树的边来表示字符，从根节点到任意节点的路径就构成一个前缀。每个节点包含一个children数组（比如26个字母就是长度26的数组）和一个isEnd标记表示是否是完整单词。插入和查询的时间复杂度都是O(m)，m是字符串长度，跟存了多少个词无关，这是它相比HashMap做前缀匹配的核心优势——HashMap只能精确查找，不支持前缀查询。实际应用中，搜索引擎的自动补全、IDE的代码提示、IP路由表的最长前缀匹配都用到Trie。空间方面，如果字符集很大会导致空间爆炸，可以用压缩Trie（Radix Tree）把只有一个子节点的路径合并来优化。

追问与易错

追问方向：

“Trie 树的空间优化？”→ 用数组压缩（只分配实际使用的子节点）、双数组 Trie（base+check 数组）、或用 HashMap 替代固定大小的 children 数组来减少空间浪费
“Trie 和 HashMap 前缀匹配的区别？”→ Trie 天然支持前缀搜索和自动补全，沿路径走即可；HashMap 只能精确匹配，前缀查询需遍历所有 key 逐一判断，效率低
“压缩 Trie 了解吗？”→ 又叫 Patricia Tree / Radix Tree，将只有单个子节点的连续边合并为一条边存储整个字符串片段，大幅减少节点数和空间占用

易错点：

❌ Trie 树空间效率高——字符集大时空间爆炸
❌ HashMap 也能前缀匹配——HashMap 不支持前缀查询