什么是字典树（Trie）？它的结构和特点是什么？

简化版

字典树（Trie，又叫前缀树）是一棵多叉树，专门用来存储和检索字符串集合。它的核心思想是「用路径表示字符串、公共前缀共享节点」：从根到某个节点走过的边（字符）拼起来，就是一个字符串前缀。查一个长度为 L 的单词只需 O(L) 时间，和存了多少单词无关。特别擅长前缀匹配（自动补全、敏感词过滤）。

详细版

结构：

根节点为空（不代表任何字符）。
每条边代表一个字符，从根到某节点的路径拼成一个前缀。
每个节点通常存：children（指向子节点，可用数组或哈希表）+ isEnd（标记「从根到这里是否构成一个完整的单词」）。

存入 {"cat", "car", "card", "dog"} 的 Trie：

        (root)
        /    \
       c      d
       |      |
       a      o
      / \     |
     t   r    g(end)
   (end)  \
          (end)  d(end)   ← car / card 共享 "car" 前缀

三大特点：

公共前缀共享：cat、car、card 共用 c→a 这段路径，省空间也是它的优势来源。
O(L) 检索：查找/插入只和字符串长度 L 有关，与集合大小无关。
天然支持前缀操作：判断「有没有以某前缀开头的单词」只需顺着前缀走一遍。

完整版教学

一、Trie 要解决什么问题

假如你要维护一个很大的字符串集合，频繁地做这些操作：判断某个词在不在、有没有以某段前缀开头的词、按字典序列出所有词……用哈希表能做等值查找，但前缀相关的操作它无能为力（哈希把字符串打散了，前缀信息全丢了）。Trie 的设计正是「把字符串按字符逐个拆开、沿树存储」，于是前缀天然体现在树的路径里，前缀操作变得非常自然。

二、路径即字符串：核心思想

Trie 最妙的地方是「用位置编码信息」——一个字符串不是存在某个节点里，而是体现为「从根走到某节点的这条路径」。所以：

走 c→a→t 到达的节点，就代表前缀 cat。
如果这个节点 isEnd=true，说明 cat 是集合里的一个完整单词；否则它只是别的单词（如 catch）的前缀。

这个「路径表示字符串」的思想，让公共前缀自动共享同一段路径。

三、isEnd 标记为什么必不可少

只有路径还不够，必须有 isEnd 来区分两种情况：

完整单词：cat 存进去了，t 节点 isEnd=true。
仅是前缀：如果只存了 catch，那走到 cat 的 t 节点时 isEnd=false——cat 只是 catch 的前缀，不是一个被收录的单词。

没有 isEnd，就分不清「这个词真的存在」和「它只是某个更长词的前缀」。这是 Trie 实现里最容易漏的点。

四、children 用数组还是哈希表

每个节点的子节点有两种常见存法：

定长数组（如小写字母用 TrieNode[26]）：下标直接对应字符，访问 O(1)、快；但即使只有几个孩子也占 26 个指针，空间浪费大。
哈希表（Map<Character, TrieNode>）：只存实际存在的孩子，省空间，但有哈希开销、常数大。

字符集小（26 字母）常用数组；字符集大（Unicode、中文）用哈希表。这是 Trie「空间换时间」权衡的一个体现。

五、Trie 擅长和不擅长什么

擅长：前缀匹配、自动补全、判断词是否存在、按字典序遍历、多模式串匹配（配合 AC 自动机）。
不擅长：空间开销大（节点多、指针稀疏）；不适合做「子串」查找（它是前缀结构，不是后缀/子串结构，子串匹配用后缀树/自动机或 KMP）。

六、常见误区与追问

考点	正确口径
节点含义	代表某个前缀
边含义	从父前缀追加一个字符
isEnd	标记该前缀是否是完整单词

root
 └─ c
    └─ a
       ├─ t (isEnd)
       └─ r (isEnd)

Trie 里路径才对应字符串，节点本身通常只保存孩子和终止标记。

误区：走到某个节点就表示一个单词存在。 只有 isEnd=true 才表示完整单词存在，否则可能只是某个前缀。
误区：Trie 查询复杂度和词库大小直接相关。 单词查找主要与待查字符串长度 L 相关，而不是词库有多少词。
误区：Trie 一定比哈希表省空间。 如果公共前缀少或字符集大，孩子指针会带来明显空间开销。
追问：children 用数组还是哈希表？ 字符集小且固定可用数组，速度快；字符集大或稀疏可用哈希表省空间。
追问：Trie 适合哪些操作？ 前缀查询、自动补全、字典序遍历、多模式匹配等。
追问：空字符串如何处理？ 可在 root 上设置 isEnd，具体看题目是否允许空字符串。

七、加强记忆

字典树（Trie/前缀树）是多叉树，核心思想「路径表示字符串、公共前缀共享节点」：根为空、边代表字符、isEnd 标记完整单词。查找/插入 O(L)（只和串长有关，与集合大小无关），天然擅长前缀操作（自动补全、敏感词）。children 用数组（快、费空间）或哈希表（省空间、常数大）。别漏 isEnd——它区分「完整单词」和「只是前缀」。缺点是空间开销大、不适合子串查找。

简化版

详细版