题目描述
思路解析
一句话答案：LeetCode 208 实现 Trie（前缀树）只需给每个节点两样东西：children 映射（字母到子节点）和 isEnd 标记。insert 逐字母下行、缺边就新建、末尾打 isEnd；search 要求路走通且终点 isEnd 为真；startsWith 只看路通不通。三种操作时间都是 O(L)，L 为单词长度，与已存单词数无关。
前缀树到底在解决什么问题
哈希集合能瞬间回答「这个完整单词存过没有」，却答不了「有没有单词以 ca 开头」——除非把整个词库翻一遍。前缀树（Trie）换一种存法：把每个单词拆成一条从根出发的字母路径，拥有相同前缀的单词共用同一段路。于是查前缀变成沿路径走一遍，走通即存在，耗时只和前缀长度有关，与词库大小无关。这也是它天然支持自动补全、前缀枚举的原因。
节点为什么只需要 children 和 isEnd
Trie 节点不存字母本身——字母藏在「父到子」这条边上，也就是 children 映射的键里。节点真正要记的只有两件事：往下还有哪些字母可走（children），以及有没有单词恰好在此结束（isEnd）。isEnd 是本题的灵魂：插入 cat 之后，c 到 a 这条路是通的，但词库里并没有 ca 这个词——不打标记，就区分不了「某个单词路过的中间点」和「某个单词的终点」。
insert 为什么缺边才新建节点
插入时逐字母下行：children 里已有这条边就直接复用，缺了才新建节点，走到单词末尾把该节点的 isEnd 设为 true。「有则复用、缺才新建」正是前缀共享的来源——先插 cat 再插 car，c、a 两步都在走老路，只在第三个字母处分叉新建。反过来，如果不判断存在与否、每个字母都无脑新建，会把原来挂在该位置下的子树连同 isEnd 标记整个顶掉，之前插入的单词就悄悄丢了。
search 和 startsWith 只差一个判断
两个查询共用同一段走路逻辑：从根出发逐字母找边，任何一步找不到就直接失败。差别只在终点处多问一句：search 还要求终点节点的 isEnd 为 true，startsWith 路通即可、不看 isEnd。所以插入 cat、car、card 之后，查完整单词 ca 返回 false——路能走通，但没有单词恰好叫 ca；查前缀 ca 返回 true——三个词都以它开头。把 isEnd 检查错加进 startsWith，会把合法前缀误判为不存在。
复杂度为什么只看单词长度
insert、search、startsWith 都是沿单词逐字母走一遍，时间 O(L)，L 为单词长度——词库里存了多少词都不影响单次操作的步数，这是 Trie 相对线性扫描的核心优势。空间最坏 O(N·L)，即 N 个单词的每个字母都新建节点，实际因公共前缀共享通常小得多。实现上，字符集只有 26 个小写字母时 children 用定长数组访问最快；字符集大或稀疏时用哈希表更省空间，两者复杂度相同。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记牢三句话：insert 缺字母就补、终点打 isEnd；search 要到终点且 isEnd 为真；startsWith 只看路通不通。下面把每步沿树走给你看。
insert("cat")：从根节点出发，等会儿一个字母一个字母地往下找路。
第 1 个字母 'c'：之前没有这条边，新建一个节点，指针走到 'c'。
第 2 个字母 'a'：之前没有这条边，新建一个节点，指针走到 'a'。
第 3 个字母 't'：之前没有这条边，新建一个节点，指针走到 't'。
走到末尾字母 't'，把它的 isEnd 标记设为 true（绿色），表示“cat”这个完整单词到这里结束。插入完成。
insert("car")：从根节点出发，等会儿一个字母一个字母地往下找路。
第 1 个字母 'c'：这条边已经存在，直接复用，指针走到 'c'。
第 2 个字母 'a'：这条边已经存在，直接复用，指针走到 'a'。
第 3 个字母 'r'：之前没有这条边，新建一个节点，指针走到 'r'。
走到末尾字母 'r'，把它的 isEnd 标记设为 true（绿色），表示“car”这个完整单词到这里结束。插入完成。
insert("card")：从根节点出发，等会儿一个字母一个字母地往下找路。
第 1 个字母 'c'：这条边已经存在，直接复用，指针走到 'c'。
第 2 个字母 'a'：这条边已经存在，直接复用，指针走到 'a'。
第 3 个字母 'r'：这条边已经存在，直接复用，指针走到 'r'。
第 4 个字母 'd'：之前没有这条边，新建一个节点，指针走到 'd'。
走到末尾字母 'd'，把它的 isEnd 标记设为 true（绿色），表示“card”这个完整单词到这里结束。插入完成。
search("car")：从根节点出发，等会儿一个字母一个字母地往下找路。
第 1 个字母 'c'：从当前节点的孩子里能找到 'c'，指针顺着走下去。
第 2 个字母 'a'：从当前节点的孩子里能找到 'a'，指针顺着走下去。
第 3 个字母 'r'：从当前节点的孩子里能找到 'r'，指针顺着走下去。
路径走到末尾节点 'r'，它的 isEnd 是 true，说明“car”确实作为完整单词存过，返回 true。
search("ca")：还是从根出发，逐字母往下走。
第 1 个字母 'c'：孩子里有这条边，指针走到 'c'。
第 2 个字母 'a'：孩子里有这条边，指针走到 'a'。
两个字母都走通了，但停在 'a' 节点——它的 isEnd 是 false（没有单词正好叫 “ca”），所以 search 返回 false。
startsWith("ca")：同样从根出发，只要每个字母都能走通就行。
第 1 个字母 'c'：能走通，指针走到 'c'。
第 2 个字母 'a'：能走通，指针走到 'a'。
“ca” 的两个字母都走通了。startsWith 不看 isEnd，路通就算数，返回 true——cat/car/card 都以 ca 开头。
三个高频追问：isEnd 的意义、children 选型、以及为什么不用哈希集合。
参考代码
class Trie: def __init__(self): self.children = {} # 字母 -> 子节点 self.isEnd = False # 是否有单词在此结束 def insert(self, word): node = self for ch in word: if ch not in node.children: node.children[ch] = Trie() # 缺就新建 node = node.children[ch] node.isEnd = True # 终点打标记 def _walk(self, s): node = self for ch in s: if ch not in node.children: return None node = node.children[ch] return node def search(self, word): node = self._walk(word) return node is not None and node.isEnd def startsWith(self, prefix): return self._walk(prefix) is not None复杂度
- 时间：O(L)，每个操作沿单词长度 L 逐字母走一遍，与已存单词数量无关
- 空间：O(N·L)，最坏情况每个单词各字母都新建节点；公共前缀共享后通常远小于此
易错点
面试追问把动画讲成自己的话
追问isEnd 这个标记到底解决什么问题？
追问children 用数组 [26] 还是哈希表更好？
追问为什么 Trie 查前缀比把单词丢进哈希集合强？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
添加与搜索单词 - 数据结构设计
LeetCode 211 · 中等 · 沿着 字典树 Trie 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题