实现 Trie (前缀树)

下面 9 步动画会按主解代码推进，而不是泛泛讲题型。

insert("app") · 按字符建一条路径：insert("app")：逐字符建一条路径 root→a→p→p。末位 p2 打上「词尾」标记(绿色 done)，表示「app 是一个完整单词」。

insert("apple") · 公共前缀直接复用：insert("apple")：前三位 app 复用已有节点(不重建)，只新建 l、e。末位 e 也标词尾(绿色 done)。这就是 Trie 共享前缀省空间的关键。

search("app") · 走到底且是词尾 → true：search("app")：沿 a→p→p 走到末位 p2，它是绿色词尾节点 → 是完整单词 → 返回 true。

search("ap") · 路径在但不是词尾 → false：search("ap")：走到 p1 停下(高亮的当前节点)，它不是绿色词尾；真正的词尾是它后面的 p2(绿)。所以 "ap" 不是完整单词 → 返回 false。

startsWith("ap") · 只看路径在不在 → true：startsWith("ap")：和上一步走到完全相同的 p1，但这次只问「路径走得通吗」——能走到就行，不看后面 p2 是不是绿色词尾 → 返回 true。search 与 startsWith 唯一的区别就在这里。

记住这题的代码骨架：题意约束先落到状态变量，再用循环或递归维护它。

迁移阶梯：把这题练到能复述后，再去同类题里迁移：先复用状态定义，再调整边界条件。

边界三连：边界三连：极端输入先过一遍。

几个高频追问，记住答法。