实现 Trie (前缀树) 图解题解

前缀树到底在解决什么问题

哈希集合能瞬间回答「这个完整单词存过没有」，却答不了「有没有单词以 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 用定长数组访问最快；字符集大或稀疏时用哈希表更省空间，两者复杂度相同。

Python

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

C++

class Trie {
    Trie* children[26] = {};
    bool isEnd = false;
    Trie* walk(const string& s){
        Trie* node = this;
        for (char c : s){
            int i = c - 'a';
            if (!node->children[i]) return nullptr;
            node = node->children[i];
        }
        return node;
    }
public:
    void insert(string w){
        Trie* node = this;
        for (char c : w){
            int i = c - 'a';
            if (!node->children[i]) node->children[i] = new Trie();
            node = node->children[i];
        }
        node->isEnd = true;
    }
    bool search(string w){ Trie* n = walk(w); return n && n->isEnd; }
    bool startsWith(string p){ return walk(p) != nullptr; }
};

Java

class Trie {
    private Trie[] children = new Trie[26];
    private boolean isEnd = false;
    private Trie walk(String s){
        Trie node = this;
        for (char c : s.toCharArray()){
            int i = c - 'a';
            if (node.children[i] == null) return null;
            node = node.children[i];
        }
        return node;
    }
    public void insert(String w){
        Trie node = this;
        for (char c : w.toCharArray()){
            int i = c - 'a';
            if (node.children[i] == null) node.children[i] = new Trie();
            node = node.children[i];
        }
        node.isEnd = true;
    }
    public boolean search(String w){ Trie n = walk(w); return n != null && n.isEnd; }
    public boolean startsWith(String p){ return walk(p) != null; }