字典树如何删除一个单词？

简化版

先沿字符找到单词末尾节点，把它的 isEnd 置为 false（逻辑删除，最简单）。如果还想回收空间，就从末尾往回走，删掉那些「既没有子节点、又不是其它单词结尾」的无用节点——但一旦遇到「还有子节点」或「是别的单词结尾」的节点就必须停下，因为那些节点还被其它单词用着，删了会误伤。

详细版

删除的关键是不能误删还被其它单词共享的节点。分两种做法：

① 逻辑删除（最简单、最安全）：找到单词末节点，isEnd = false 即可。节点还留着（可能被别的词用），只是不再把这个词算作「存在」。实现简单，代价是空间不回收。

② 物理删除（回收空间，递归自底向上）：

// 返回值：当前节点在处理完后是否可以被父节点删除
boolean delete(Trie node, String word, int i) {
    if (i == word.length()) {
        if (!node.isEnd) return false;   // 这个词本来就不存在
        node.isEnd = false;              // 取消单词标记
        return node.hasNoChildren();     // 没有孩子才可被删
    }
    int idx = word.charAt(i) - 'a';
    Trie child = node.children[idx];
    if (child == null) return false;     // 词不存在
    if (delete(child, word, i + 1)) {    // 子节点可删
        node.children[idx] = null;       // 断开它
    }
    // 当前节点：只有「自己不是别的词结尾 且 没有其它孩子」才可继续被删
    return !node.isEnd && node.hasNoChildren();
}

完整版教学

一、删除的难点：节点是共享的

Trie 的节点被多个单词共享（公共前缀）。删 car 时，如果 Trie 里还有 card、cat，那 c、a 节点被 card、cat 用着，绝不能删；car 的 r 节点还是 card 的前缀路径（r 有子节点 d），也不能删。删除的本质不是「删路径」，而是「取消这个词的存在标记，并只回收那些完全没用了的节点」。

二、逻辑删除：把 isEnd 关掉

最简单安全的做法：找到单词末尾节点，把 isEnd 设为 false。这样 search(word) 就会返回 false（走通了但 isEnd 是 false）。节点结构一点不动，绝不会误伤其它单词。缺点是删了很多词后会残留一堆没用的节点，空间不回收。如果删除不频繁、不在意那点空间，逻辑删除足够了。

三、物理删除：自底向上、遇障即停

要真正回收空间，就得删掉无用节点。核心规则：一个节点可以被删，当且仅当它「不是任何单词的结尾（isEnd=false）」且「没有任何子节点」。用递归自底向上处理：

先递归到单词末尾，把 isEnd 置 false。
递归返回时，逐层判断「当前节点还有用吗」：
- 如果它还有其它子节点（是别的词的前缀路径）→ 有用，停止删除。
- 如果它是另一个单词的结尾（isEnd=true）→ 有用，停止。
- 否则（无孩子且非结尾）→ 无用，父节点把它断开。

一旦向上遇到「有用」的节点就停——上面的节点肯定也有用（它们是这个有用节点的祖先）。

四、走一个例子

Trie 里有 {"car", "card"}，删除 "card"：
- 走到 card 的 d 节点，isEnd=false
- d 无子节点、非其它词结尾 → 可删，断开 r→d
- 回到 r 节点：它是 "car" 的结尾（isEnd=true）→ 有用，停止！
结果：card 的 d 被回收，car 完好无损 ✓

反过来删 "car"（保留 card）：
- 走到 r 节点，isEnd=false
- 但 r 有子节点 d（card 的路径）→ 有用，停止，什么都不删
- car 仅仅是 isEnd 被关掉，路径因 card 保留 ✓

五、易错点

必须判「有没有其它孩子」和「是不是别的词结尾」，漏判就会误删共享节点。
先确认单词存在（末节点 isEnd 为 true）再删，否则可能删掉别的词的前缀。
删除不频繁时优先用逻辑删除（isEnd=false），简单且零风险。

六、常见误区与追问

考点	正确口径
逻辑删除	只关闭单词末尾 `isEnd`
物理删除	自底向上删除不再被共享的节点
停止条件	节点仍是其他单词结尾或仍有孩子

delete(word, depth):
  if depth == len: unset isEnd
  recurse child
  remove child if child has no children and !isEnd

删除 Trie 节点时最怕误删共享前缀，必须从单词末尾向上判断是否还能被别人使用。

误区：删除单词就是把路径上所有节点删掉。 这些节点可能还是其他单词的前缀，直接删除会破坏其他词。
误区：只关闭 isEnd 一定足够。 逻辑删除正确但可能留下无用节点；是否物理清理看空间需求。
误区：遇到共享节点还继续向上删。 一旦节点有孩子或本身是其他单词结尾，就必须停止清理。
追问：删除不存在的单词怎么办？ 查找过程中缺边或末尾 isEnd=false，应返回失败并不修改结构。
追问：为什么自底向上？ 只有处理完子节点后，才能判断当前节点是否变成无用节点。
追问：复杂度是多少？ 查找和回溯都沿单词长度，时间 O(L)，递归栈 O(L)。

七、加强记忆

Trie 删除先找到末节点把 isEnd 置 false（逻辑删除，安全但不回收空间）。要回收空间就自底向上物理删除：一个节点仅当「isEnd=false 且没有任何子节点」才可删，向上一遇到「还有孩子」或「是别的词结尾」的节点就停（它还被共享，删了误伤）。例：删 card 保留 car，只回收 d，走到 r（car 结尾）就停。删除不频繁优先逻辑删除。

简化版

详细版