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

这道题到底在问什么

操作

insert/search/startsWith

输出

按操作返回

最优解：一步一步想明白

1. 3下面 9 步动画会按主解代码推进，而不是泛泛讲题型。
2. 4前缀树：每条边一个字符，路径=一个前缀insert("app")：逐字符建一条路径 root→a→p→p。末位 p2 打上「词尾」标记(绿色 done)，表示「app 是一个完整单词」。
3. 5app 已存在 → 只新建 l、einsert("apple")：前三位 app 复用已有节点(不重建)，只新建 l、e。末位 e 也标词尾(绿色 done)。这就是 Trie 共享前缀省空间的关键。
4. 6沿路径走 + 检查终点词尾标记search("app")：沿 a→p→p 走到末位 p2，它是绿色词尾节点 → 是完整单词 → 返回 true。
5. 7终点没有词尾标记search("ap")：走到 p1 停下(高亮的当前节点)，它不是绿色词尾；真正的词尾是它后面的 p2(绿)。所以 "ap" 不是完整单词 → 返回 false。
6. 8前缀查询不检查词尾startsWith("ap")：和上一步走到完全相同的 p1，但这次只问「路径走得通吗」——能走到就行，不看后面 p2 是不是绿色词尾 → 返回 true。search 与 startsWith 唯一的区别就在这里。
7. 11记住这题的代码骨架：题意约束先落到状态变量，再用循环或递归维护它。
8. 16把这题练到能复述后，再去同类题里迁移：先复用状态定义，再调整边界条件。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

class Trie:
    def __init__(self):
        self.root = {}

    def insert(self, word):
        node = self.root
        for ch in word:
            node = node.setdefault(ch, {})
        node['#'] = True

    def search(self, word):
        node = self.root
        for ch in word:
            if ch not in node:
                return False
            node = node[ch]
        return '#' in node

    def startsWith(self, prefix):
        node = self.root
        for ch in prefix:
            if ch not in node:
                return False
            node = node[ch]
        return True

class Trie {
    struct Node { Node* ch[26] = {}; bool end = false; };
    Node* root = new Node();
    Node* find(const string& w) {
        Node* node = root;
        for (char c : w) { if (!node->ch[c-'a']) return nullptr; node = node->ch[c-'a']; }
        return node;
    }
public:
    void insert(string word) {
        Node* node = root;
        for (char c : word) { if (!node->ch[c-'a']) node->ch[c-'a'] = new Node(); node = node->ch[c-'a']; }
        node->end = true;
    }
    bool search(string word) { Node* n = find(word); return n && n->end; }
    bool startsWith(string prefix) { return find(prefix) != nullptr; }
};

class Trie {
    Node root = new Node();
    class Node { Node[] ch = new Node[26]; boolean end = false; }
    private Node find(String w) {
        Node node = root;
        for (char c : w.toCharArray()) { if (node.ch[c-'a'] == null) return null; node = node.ch[c-'a']; }
        return node;
    }
    public void insert(String word) {
        Node node = root;
        for (char c : word.toCharArray()) { if (node.ch[c-'a'] == null) node.ch[c-'a'] = new Node(); node = node.ch[c-'a']; }
        node.end = true;
    }
    public boolean search(String word) { Node n = find(word); return n != null && n.end; }
    public boolean startsWith(String prefix) { return find(prefix) != null; }
}

复杂度

面试官可能追问