作者：labuladong

公眾號：labuladong

讀完本文，可以去力扣解決如下題目：

208. 實(shí)現(xiàn) Trie (前綴樹)（Medium）

1804. 實(shí)現(xiàn) Trie （前綴樹） II（Medium）

648. 單詞替換（Medium）

211. 添加與搜索單詞（Medium）

677. 鍵值映射（Medium）

Trie 樹又叫字典樹、前綴樹、單詞查找樹，是一種二叉樹衍生出來的高級數(shù)據(jù)結(jié)構(gòu)，主要應(yīng)用場景是處理字符串前綴相關(guān)的操作。

后臺有挺多讀者說今年的面試筆試題涉及到這種數(shù)據(jù)結(jié)構(gòu)了，所以請我講一講。

幾年前我在《算法 4》第一次學(xué)到這種數(shù)據(jù)結(jié)構(gòu)，不過個(gè)人認(rèn)為講解不是特別通俗易懂，所以本文按照我的邏輯幫大家重新梳理一遍 Trie 樹的原理，并基于《算法 4》的代碼實(shí)現(xiàn)一套更通用易懂的代碼模板，用于處理力扣上一系列字符串前綴問題。

閱讀本文之前希望你讀過我舊文講過的回溯算法代碼模板和手把手刷二叉樹（總結(jié)篇）。

本文主要分三部分：

1、講解 Trie 樹的工作原理。

2、給出一套TrieMap和TrieSet的代碼模板，實(shí)現(xiàn)幾個(gè)常用 API。

3、實(shí)踐環(huán)節(jié)，直接套代碼模板秒殺 5 道算法題。本來可以秒殺七八道題，篇幅考慮，剩下的我集成到刷題插件中。

關(guān)于Map和Set，是兩個(gè)抽象數(shù)據(jù)結(jié)構(gòu)（接口），Map存儲一個(gè)鍵值對集合，其中鍵不重復(fù)，Set存儲一個(gè)不重復(fù)的元素集合。

常見的Map和Set的底層實(shí)現(xiàn)原理有哈希表和二叉搜索樹兩種，比如 Java 的 HashMap/HashSet 和 C++ 的 unorderd_map/unordered_set 底層就是用哈希表實(shí)現(xiàn)，而 Java 的 TreeMap/TreeSet 和 C++ 的 map/set 底層使用紅黑樹這種自平衡 BST 實(shí)現(xiàn)的。

而本文實(shí)現(xiàn)的 TrieSet/TrieMap 底層則用 Trie 樹這種結(jié)構(gòu)來實(shí)現(xiàn)。

了解數(shù)據(jù)結(jié)構(gòu)的讀者應(yīng)該知道，本質(zhì)上Set可以視為一種特殊的Map，Set其實(shí)就是Map中的鍵。

所以本文先實(shí)現(xiàn)TrieMap，然后在TrieMap的基礎(chǔ)上封裝出TrieSet。

PS：為了模板通用性的考慮，后文會用到 Java 的泛型，也就是用尖括號<>指定的類型變量。這些類型變量的作用是指定我們實(shí)現(xiàn)的容器中存儲的數(shù)據(jù)類型，類比 Java 標(biāo)準(zhǔn)庫的那些容器的用法應(yīng)該不難理解。

前文學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的框架思維說過，各種亂七八糟的結(jié)構(gòu)都是為了在「特定場景」下盡可能高效地進(jìn)行增刪查改。

你比如HashMap的優(yōu)勢是能夠在 O(1) 時(shí)間通過鍵查找對應(yīng)的值，但要求鍵的類型K必須是「可哈?！沟?；而TreeMap的特點(diǎn)是方便根據(jù)鍵的大小進(jìn)行操作，但要求鍵的類型K必須是「可比較」的。

本文要實(shí)現(xiàn)的TrieMap也是類似的，由于 Trie 樹原理，我們要求TrieMap的鍵必須是字符串類型，值的類型V可以隨意。

接下來我們了解一下 Trie 樹的原理，看看為什么這種數(shù)據(jù)結(jié)構(gòu)能夠高效操作字符串。

Trie 樹原理

Trie 樹本質(zhì)上就是一棵從二叉樹衍生出來的多叉樹。

二叉樹節(jié)點(diǎn)的代碼實(shí)現(xiàn)是這樣：

/*基本的二叉樹節(jié)點(diǎn)*/
classTreeNode{
intval;
TreeNodeleft,right;
}

其中left, right存儲左右子節(jié)點(diǎn)的指針，所以二叉樹的結(jié)構(gòu)是這樣：

多叉樹節(jié)點(diǎn)的代碼實(shí)現(xiàn)是這樣：

/*基本的多叉樹節(jié)點(diǎn)*/
classTreeNode{
intval;
TreeNode[]children;
}

其中children數(shù)組中存儲指向孩子節(jié)點(diǎn)的指針，所以多叉樹的結(jié)構(gòu)是這樣：

而TrieMap中的樹節(jié)點(diǎn)TrieNode的代碼實(shí)現(xiàn)是這樣：

/*Trie樹節(jié)點(diǎn)實(shí)現(xiàn)*/
classTrieNode<V>{
Vval=null;
TrieNode[]children=newTrieNode[256];
}

這個(gè)val字段存儲鍵對應(yīng)的值，children數(shù)組存儲指向子節(jié)點(diǎn)的指針。

但是和之前的普通多叉樹節(jié)點(diǎn)不同，TrieNode中children數(shù)組的索引是有意義的，代表鍵中的一個(gè)字符。

比如說children[97]如果非空，說明這里存儲了一個(gè)字符'a'，因?yàn)?code style="margin-right:2px;margin-left:2px;padding:2px 4px;font-size:inherit;line-height:inherit;color:rgb(233,105,0);background:rgb(248,248,248);">'a'的 ASCII 碼為 97。

我們的模板只考慮處理 ASCII 字符，所以children數(shù)組的大小設(shè)置為 256。不過這個(gè)可以根據(jù)具體問題修改，比如改成更小的數(shù)組或者HashMap都是一樣的效果。

有了以上鋪墊，Trie 樹的結(jié)構(gòu)是這樣的：

一個(gè)節(jié)點(diǎn)有 256 個(gè)子節(jié)點(diǎn)指針，但大多數(shù)時(shí)候都是空的，可以省略掉不畫，所以一般你看到的 Trie 樹長這樣：

這是在TrieMap中插入一些鍵值對后的樣子，白色節(jié)點(diǎn)代表val字段為空，橙色節(jié)點(diǎn)代表val字段非空。

這里要特別注意，TrieNode節(jié)點(diǎn)本身只存儲val字段，并沒有一個(gè)字段來存儲字符，字符是通過子節(jié)點(diǎn)在父節(jié)點(diǎn)的children數(shù)組中的索引確定的。

形象理解就是，Trie 樹用「樹枝」存儲字符串（鍵），用「節(jié)點(diǎn)」存儲字符串（鍵）對應(yīng)的數(shù)據(jù)（值）。所以我在圖中把字符標(biāo)在樹枝，鍵對應(yīng)的值val標(biāo)在節(jié)點(diǎn)上：

明白這一點(diǎn)很重要，有助于之后你理解代碼實(shí)現(xiàn)。

PS：《算法 4》以及網(wǎng)上講 Trie 樹的很多文章中都是把字符標(biāo)在節(jié)點(diǎn)上，我認(rèn)為這樣很容易讓初學(xué)者產(chǎn)生誤解，所以建議大家按照我的這種理解來記憶 Trie 樹結(jié)構(gòu)。

現(xiàn)在你應(yīng)該知道為啥 Trie 樹也叫前綴樹了，因?yàn)槠渲械淖址蚕砬熬Y，相同前綴的字符串集中在 Trie 樹中的一個(gè)子樹上，給字符串的處理帶來很大的便利。

TrieMap/TrieSet API 及實(shí)現(xiàn)

首先我們看一下本文實(shí)現(xiàn)的TrieMap的 API，為了舉例 API 的功能，假設(shè) TrieMap 中已經(jīng)存儲了如下鍵值對：

//底層用Trie樹實(shí)現(xiàn)的鍵值映射
//鍵為String類型，值為類型VclassTrieMap<V>{

/*****增/改*****/

//在Map中添加key
publicvoidput(Stringkey,Vval);

/*****刪*****/

//刪除鍵key以及對應(yīng)的值
publicvoidremove(Stringkey);

/*****查*****/

//搜索key對應(yīng)的值，不存在則返回null
//get("the")->4
//get("tha")->null
publicVget(Stringkey);

//判斷key是否存在在Map中
//containsKey("tea")->false
//containsKey("team")->true
publicbooleancontainsKey(Stringkey);

//在Map的所有鍵中搜索query的最短前綴
//shortestPrefixOf("themxyz")->"the"
publicStringshortestPrefixOf(Stringquery);

//在Map的所有鍵中搜索query的最長前綴
//longestPrefixOf("themxyz")->"them"
publicStringlongestPrefixOf(Stringquery);

//搜索所有前綴為prefix的鍵
//keysWithPrefix("th")->["that","the","them"]
publicListkeysWithPrefix(Stringprefix);

//判斷是和否存在前綴為prefix的鍵
//hasKeyWithPrefix("tha")->true
//hasKeyWithPrefix("apple")->false
publicbooleanhasKeyWithPrefix(Stringprefix);

//通配符.匹配任意字符，搜索所有匹配的鍵
//keysWithPattern("t.a.")->["team","that"]
publicListkeysWithPattern(Stringpattern);

//通配符.匹配任意字符，判斷是否存在匹配的鍵
//hasKeyWithPattern(".ip")->true
//hasKeyWithPattern(".i")->false
publicbooleanhasKeyWithPattern(Stringpattern);

//返回Map中鍵值對的數(shù)量
publicintsize();
}

至于TrieSet的 API 大同小異，所以這里不重復(fù)列舉，后文直接給出實(shí)現(xiàn)。

接下來是重頭戲，我們一個(gè)一個(gè)實(shí)現(xiàn)TrieMap的上述 API 函數(shù)。

首先，TrieMap類中一定需要記錄 Trie 的根節(jié)點(diǎn)root，以及 Trie 樹中的所有節(jié)點(diǎn)數(shù)量用于實(shí)現(xiàn)size()方法：

classTrieMap<V>{
//ASCII碼個(gè)數(shù)
privatestaticfinalintR=256;
//當(dāng)前存在Map中的鍵值對個(gè)數(shù)
privateintsize=0;

privatestaticclassTrieNode<V>{
Vval=null;
TrieNode[]children=newTrieNode[R];
}

//Trie樹的根節(jié)點(diǎn)
privateTrieNoderoot=null;

/*其他API的實(shí)現(xiàn)...*/

publicintsize(){
returnsize;
}
}

另外，我們再實(shí)現(xiàn)一個(gè)工具函數(shù)getNode：

//從節(jié)點(diǎn)node開始搜索key，如果存在返回對應(yīng)節(jié)點(diǎn)，否則返回null
privateTrieNodegetNode(TrieNodenode,Stringkey){
TrieNodep=node;
//從節(jié)點(diǎn)node開始搜索key
for(inti=0;iif(p==null){
//無法向下搜索
returnnull;
}
//向下搜索
charc=key.charAt(i);
p=p.children[c];
}
returnp;
}

有了這個(gè)getNode函數(shù)，就能實(shí)現(xiàn)containsKey方法和get方法了：

//搜索key對應(yīng)的值，不存在則返回null
publicVget(Stringkey){
//從root開始搜索key
TrieNodex=getNode(root,key);
if(x==null||x.val==null){
//x為空或x的val字段為空都說明key沒有對應(yīng)的值
returnnull;
}
returnx.val;
}

//判斷key是否存在在Map中
publicbooleancontainsKey(Stringkey){
returnget(key)!=null;
}

這里需要注意，就算getNode(key)的返回值x非空，也只能說字符串key是一個(gè)「前綴」；除非x.val同時(shí)非空，才能判斷鍵key存在。

不過，這個(gè)特性恰好能夠幫我們實(shí)現(xiàn)hasKeyWithPrefix方法：

//判斷是和否存在前綴為prefix的鍵
publicbooleanhasKeyWithPrefix(Stringprefix){
//只要能找到 prefix 對應(yīng)的節(jié)點(diǎn)，就是存在前綴
returngetNode(root,prefix)!=null;
}

類似getNode方法的邏輯，我們可以實(shí)現(xiàn)shortestPrefixOf方法，只要在第一次遇到存有val的節(jié)點(diǎn)的時(shí)候返回就行了：

//在所有鍵中尋找query的最短前綴
publicStringshortestPrefixOf(Stringquery){
TrieNodep=root;
//從節(jié)點(diǎn)node開始搜索key
for(inti=0;iif(p==null){
//無法向下搜索
return"";
}
if(p.val!=null){
//找到一個(gè)鍵是query的前綴
returnquery.substring(0,i);
}
//向下搜索
charc=query.charAt(i);
p=p.children[c];
}

if(p!=null&&p.val!=null){
//如果query本身就是一個(gè)鍵
returnquery;
}
return"";
}

這里需要注意的是 for 循環(huán)結(jié)束之后我們還需要額外檢查一下。

因?yàn)橹罢f了 Trie 樹中「樹枝」存儲字符串，「節(jié)點(diǎn)」存儲字符串對應(yīng)的值，for 循環(huán)相當(dāng)于只遍歷了「樹枝」，但漏掉了最后一個(gè)「節(jié)點(diǎn)」，即query本身就是TrieMap中的一個(gè)鍵的情況。

如果你理解了shortestPrefixOf的實(shí)現(xiàn)，那么longestPrefixOf也是非常類似的：

//在所有鍵中尋找query的最長前綴
publicStringlongestPrefixOf(Stringquery){
TrieNodep=root;
//記錄前綴的最大長度
intmax_len=0;

//從節(jié)點(diǎn)node開始搜索key
for(inti=0;iif(p==null){
//無法向下搜索
break;
}
if(p.val!=null){
//找到一個(gè)鍵是query的前綴，更新前綴的最大長度
max_len=i;
}
//向下搜索
charc=query.charAt(i);
p=p.children[c];
}

if(p!=null&&p.val!=null){
//如果query本身就是一個(gè)鍵
returnquery;
}
returnquery.substring(0,max_len);
}

每次遇到p.val非空的時(shí)候說明找到一個(gè)鍵，但是我們不急著返回，而是更新max_len變量，記錄最長前綴的長度。

同樣的，在 for 循環(huán)結(jié)束時(shí)還是要特殊判斷一下，處理query本身就是鍵的情況。

接下來，我們來實(shí)現(xiàn)keysWithPrefix方法，得到所有前綴為prefix的鍵。

看過前文手把手刷二叉樹（總結(jié)篇）的讀者應(yīng)該可以想到，先利用getNode函數(shù)在 Trie 樹中找到prefix對應(yīng)的節(jié)點(diǎn)x，然施展多叉樹的遍歷算法，遍歷以x為根的這棵 Trie 樹，找到所有鍵值對：

代碼實(shí)現(xiàn)如下：

//搜索前綴為prefix的所有鍵
publicListkeysWithPrefix(Stringprefix){
Listres=newLinkedList<>();
//找到匹配prefix在Trie樹中的那個(gè)節(jié)點(diǎn)
TrieNodex=getNode(root,prefix);
if(x==null){
returnres;
}
//DFS遍歷以x為根的這棵Trie樹
traverse(x,newStringBuilder(prefix),res);
returnres;
}

//遍歷以node節(jié)點(diǎn)為根的Trie樹，找到所有鍵
privatevoidtraverse(TrieNodenode,StringBuilderpath,Listres){
if(node==null){
//到達(dá)Trie樹底部葉子結(jié)點(diǎn)
return;
}

if(node.val!=null){
//找到一個(gè)key，添加到結(jié)果列表中
res.add(path.toString());
}

//回溯算法遍歷框架
for(charc=0;c//做選擇
path.append(c);
traverse(node.children[c],path,res);
//撤銷選擇
path.deleteCharAt(path.length()-1);
}
}

這段代碼中traverse函數(shù)你可能看起來特別熟悉，就是回溯算法核心套路中講的回溯算法代碼框架。

關(guān)于回溯算法框架和標(biāo)準(zhǔn)多叉樹框架的區(qū)別我在圖論算法基礎(chǔ)中探討過，關(guān)鍵在于遍歷「節(jié)點(diǎn)」和遍歷「樹枝」的區(qū)別。由于 Trie 樹將字符存儲在「樹枝」上，traverse函數(shù)是在遍歷樹枝上的字符，所以采用的是回溯算法框架。

另外，再注意一下這段邏輯：

//回溯算法遍歷框架
for(charc=0;c//做選擇
path.append(c);
traverse(node.children[c],path,res);
//撤銷選擇
path.deleteCharAt(path.length()-1);
}

回顧一下我們 Trie 樹的圖：

你是否會有疑問：代碼中 for 循環(huán)會執(zhí)行 256 次，但是圖中的一個(gè)節(jié)點(diǎn)只有幾個(gè)子節(jié)點(diǎn)，也就是說每個(gè)節(jié)點(diǎn)的children數(shù)組中大部分都是空指針，這不會有問題嗎？

是不是應(yīng)該把代碼改成這樣：

//回溯算法遍歷框架
for(charc=0;c//做選擇
path.append(c);
if(node.children[c]!=null){
traverse(node.children[c],path,res);
}
//撤銷選擇
path.deleteCharAt(path.length()-1);
}

答案是，改不改都行，這兩種寫法從邏輯上講完全相同，因?yàn)?code style="margin-right:2px;margin-left:2px;padding:2px 4px;font-size:inherit;line-height:inherit;color:rgb(233,105,0);background:rgb(248,248,248);">traverse函數(shù)開始的時(shí)候如果發(fā)現(xiàn)node == null也會直接返回。

我為了保持框架的一致性，就沒有在 for 循環(huán)中判斷子節(jié)點(diǎn)是否為空，而是依賴遞歸函數(shù)的 base case。當(dāng)然你完全可以按照自己的喜好來實(shí)現(xiàn)。

下面來實(shí)現(xiàn)keysWithPattern方法，使用通配符來匹配多個(gè)鍵，其關(guān)鍵就在于通配符.可以匹配所有字符。

在代碼實(shí)現(xiàn)上，用path變量記錄匹配鍵的路徑，遇到通配符時(shí)使用類似回溯算法的框架就行了：

//通配符.匹配任意字符
publicListkeysWithPattern(Stringpattern){
Listres=newLinkedList<>();
traverse(root,newStringBuilder(),pattern,0,res);
returnres;
}

//遍歷函數(shù)，嘗試在「以node為根的Trie樹中」匹配pattern[i..]
privatevoidtraverse(TrieNodenode,StringBuilderpath,Stringpattern,inti,Listres){
if(node==null){
//樹枝不存在，即匹配失敗
return;
}
if(i==pattern.length()){
//pattern匹配完成
if(node.val!=null){
//如果這個(gè)節(jié)點(diǎn)存儲著val，則找到一個(gè)匹配的鍵
res.add(path.toString());
}
return;
}
charc=pattern.charAt(i);
if(c=='.'){
//pattern[i]是通配符，可以變化成任意字符
//多叉樹（回溯算法）遍歷框架
for(charj=0;j1,res);
path.deleteCharAt(path.length()-1);
}
}else{
//pattern[i]是普通字符c
path.append(c);
traverse(node.children[c],path,pattern,i+1,res);
path.deleteCharAt(path.length()-1);
}
}

下面這個(gè) GIF 畫了匹配"t.a."的過程，應(yīng)該就容易理解上述代碼的邏輯了：

可以看到，keysWithPattern和keysWithPrefix的實(shí)現(xiàn)是有些類似的，而且這兩個(gè)函數(shù)還有一個(gè)潛在的特性：它們返回的結(jié)果列表一定是符合「字典序」的。

原因應(yīng)該不難理解，每一個(gè)節(jié)點(diǎn)的children數(shù)組都是從左到右進(jìn)行遍歷，即按照 ASCII 碼從小到大的順序遞歸遍歷，得到的結(jié)果自然是符合字典序的。

好，現(xiàn)在我們實(shí)現(xiàn)了keysWithPattern方法得到模式串匹配的所有鍵，那你是否可以實(shí)現(xiàn)hasKeyWithPattern方法，僅僅判斷是否存在鍵匹配模式串？

//一個(gè)偷懶的實(shí)現(xiàn)
publicbooleanhasKeyWithPattern(Stringpattern){
return!keysWithPattern(pattern).isEmpty();
}

這是一個(gè)偷懶的實(shí)現(xiàn)，因?yàn)樗膹?fù)雜度比較高。我們的目的僅僅是判斷是否存在匹配模式串的鍵，你卻把所有匹配的鍵都算出來了，這顯然是沒有必要的。

我們只需稍微改寫一下keysWithPattern方法就可以高效實(shí)現(xiàn)hasKeyWithPattern方法：

//判斷是和否存在前綴為prefix的鍵
publicbooleanhasKeyWithPattern(Stringpattern){
//從root節(jié)點(diǎn)開始匹配pattern[0..]
returnhasKeyWithPattern(root,pattern,0);
}

//函數(shù)定義：從 node 節(jié)點(diǎn)開始匹配 pattern[i..]，返回是否成功匹配
privatebooleanhasKeyWithPattern(TrieNodenode,Stringpattern,inti){
if(node==null){
//樹枝不存在，即匹配失敗
returnfalse;
}
if(i==pattern.length()){
//模式串走到頭了，看看匹配到的是否是一個(gè)鍵
returnnode.val!=null;
}
charc=pattern.charAt(i);
//沒有遇到通配符
if(c!='.'){
//從node.children[c]節(jié)點(diǎn)開始匹配pattern[i+1..]
returnhasKeyWithPattern(node.children[c],pattern,i+1);
}
//遇到通配符
for(intj=0;j//pattern[i]可以變化成任意字符，嘗試所有可能，只要遇到一個(gè)匹配成功就返回
if(hasKeyWithPattern(node.children[j],pattern,i+1)){
returntrue;
}
}
//都沒有匹配
returnfalse;
}

有之前的鋪墊，這個(gè)實(shí)現(xiàn)應(yīng)該是不難理解的，類似于回溯算法解數(shù)獨(dú)游戲中找到一個(gè)可行解就提前結(jié)束遞歸的做法。

到這里，TrieMap的所有和前綴相關(guān)的方法都實(shí)現(xiàn)完了，還剩下put和remove這兩個(gè)基本方法了，其實(shí)它們的難度不大，就是遞歸修改數(shù)據(jù)結(jié)構(gòu)的那一套，如果不熟悉的話可以參見二叉搜索樹基本操作。

先說put方法的實(shí)現(xiàn)吧，直接看代碼：

//在map中添加或修改鍵值對
publicvoidput(Stringkey,Vval){
if(!containsKey(key)){
//新增鍵值對
size++;
}
//需要一個(gè)額外的輔助函數(shù)，并接收其返回值
root=put(root,key,val,0);
}

//定義：向以 node 為根的 Trie 樹中插入 key[i..]，返回插入完成后的根節(jié)點(diǎn)
privateTrieNodeput(TrieNodenode,Stringkey,Vval,inti){
if(node==null){
//如果樹枝不存在，新建
node=newTrieNode<>();
}
if(i==key.length()){
//key的路徑已插入完成，將值val存入節(jié)點(diǎn)
node.val=val;
returnnode;
}
charc=key.charAt(i);
//遞歸插入子節(jié)點(diǎn)，并接收返回值
node.children[c]=put(node.children[c],key,val,i+1);
returnnode;
}

因?yàn)槭沁f歸修改數(shù)據(jù)結(jié)構(gòu)，所以我們必須額外創(chuàng)建一個(gè)返回類型為TrieNode的輔助函數(shù)，并且在遞歸調(diào)用的時(shí)候接收其返回值，拼接到父節(jié)點(diǎn)上。

前文說了，Trie 樹中的鍵就是「樹枝」，值就是「節(jié)點(diǎn)」，所以插入的邏輯就是沿路新建「樹枝」，把key的整條「樹枝」構(gòu)建出來之后，在樹枝末端的「節(jié)點(diǎn)」中存儲val：

最后，我們說一下remove函數(shù)，似乎所有數(shù)據(jù)結(jié)構(gòu)的刪除操作相對其他操作都會更復(fù)雜一些。

比如說下圖這個(gè)場景，如果你想刪除鍵"team"，那么需要刪掉"eam"這條樹枝才是符合邏輯的：

刪多了肯定不行，但刪少了也不行，否則前文實(shí)現(xiàn)的hasKeyWithPrefix就會出錯。

那么如何控制算法來正確地進(jìn)行刪除呢？

首先，遞歸修改數(shù)據(jù)結(jié)構(gòu)的時(shí)候，如果一個(gè)節(jié)點(diǎn)想刪掉自己，直接返回空指針就行了。

其次，一個(gè)節(jié)點(diǎn)如何知道自己是否需要被刪除呢？主要看自己的val字段是否為空以及自己的children數(shù)組是否全都是空指針。

這里就要利用前文手把手刷二叉樹（總結(jié)篇）中說到的后序位置的特點(diǎn)了：

一個(gè)節(jié)點(diǎn)要先遞歸處理子樹，然后在后序位置檢查自己的val字段和children列表，判斷自己是否需要被刪除。

如果自己的val字段為空，說明自己沒有存儲值，如果同時(shí)自己的children數(shù)組全是空指針，說明自己下面也沒有接樹枝，即不是任何一個(gè)鍵的前綴。這種情況下這個(gè)節(jié)點(diǎn)就沒有存在的意義了，應(yīng)該刪掉自己。

直接看代碼：

//在Map中刪除key
publicvoidremove(Stringkey){
if(!containsKey(key)){
return;
}
//遞歸修改數(shù)據(jù)結(jié)構(gòu)要接收函數(shù)的返回值
root=remove(root,key,0);
size--;
}

//定義：在以 node 為根的 Trie 樹中刪除 key[i..]，返回刪除后的根節(jié)點(diǎn)
privateTrieNoderemove(TrieNodenode,Stringkey,inti){
if(node==null){
returnnull;
}
if(i==key.length()){
//找到了key對應(yīng)的TrieNode，刪除val
node.val=null;
}else{
charc=key.charAt(i);
//遞歸去子樹進(jìn)行刪除
node.children[c]=remove(node.children[c],key,i+1);
}
//后序位置，遞歸路徑上的節(jié)點(diǎn)可能需要被清理
if(node.val!=null){
//如果該TireNode存儲著val，不需要被清理
returnnode;
}
//檢查該TrieNode是否還有后綴
for(intc=0;cif(node.children[c]!=null){
//只要存在一個(gè)子節(jié)點(diǎn)（后綴樹枝），就不需要被清理
returnnode;
}
}
//既沒有存儲val，也沒有后綴樹枝，則該節(jié)點(diǎn)需要被清理
returnnull;
}

到這里，TrieMap的所有 API 就實(shí)現(xiàn)完了，完整代碼如下：

classTrieMap<V>{
//ASCII碼個(gè)數(shù)
privatestaticfinalintR=256;
//當(dāng)前存在Map中的鍵值對個(gè)數(shù)
privateintsize=0;
//Trie樹的根節(jié)點(diǎn)
privateTrieNoderoot=null;

privatestaticclassTrieNode<V>{
Vval=null;
TrieNode[]children=newTrieNode[R];
}

/*****增/改*****/

//在map中添加或修改鍵值對
publicvoidput(Stringkey,Vval){
if(!containsKey(key)){
//新增鍵值對
size++;
}
//需要一個(gè)額外的輔助函數(shù)，并接收其返回值
root=put(root,key,val,0);
}

//定義：向以 node 為根的 Trie 樹中插入 key[i..]，返回插入完成后的根節(jié)點(diǎn)
privateTrieNodeput(TrieNodenode,Stringkey,Vval,inti){
if(node==null){
//如果樹枝不存在，新建
node=newTrieNode<>();
}
if(i==key.length()){
//key的路徑已插入完成，將值val存入節(jié)點(diǎn)
node.val=val;
returnnode;
}
charc=key.charAt(i);
//遞歸插入子節(jié)點(diǎn)，并接收返回值
node.children[c]=put(node.children[c],key,val,i+1);
returnnode;
}

/*****刪*****/

//在Map中刪除key
publicvoidremove(Stringkey){
if(!containsKey(key)){
return;
}
//遞歸修改數(shù)據(jù)結(jié)構(gòu)要接收函數(shù)的返回值
root=remove(root,key,0);
size--;
}

//定義：在以 node 為根的 Trie 樹中刪除 key[i..]，返回刪除后的根節(jié)點(diǎn)
privateTrieNoderemove(TrieNodenode,Stringkey,inti){
if(node==null){
returnnull;
}
if(i==key.length()){
//找到了key對應(yīng)的TrieNode，刪除val
node.val=null;
}else{
charc=key.charAt(i);
//遞歸去子樹進(jìn)行刪除
node.children[c]=remove(node.children[c],key,i+1);
}
//后序位置，遞歸路徑上的節(jié)點(diǎn)可能需要被清理
if(node.val!=null){
//如果該TireNode存儲著val，不需要被清理
returnnode;
}
//檢查該TrieNode是否還有后綴
for(intc=0;cif(node.children[c]!=null){
//只要存在一個(gè)子節(jié)點(diǎn)（后綴樹枝），就不需要被清理
returnnode;
}
}
//既沒有存儲val，也沒有后綴樹枝，則該節(jié)點(diǎn)需要被清理
returnnull;
}

/*****查*****/

//搜索key對應(yīng)的值，不存在則返回null
publicVget(Stringkey){
//從root開始搜索key
TrieNodex=getNode(root,key);
if(x==null||x.val==null){
//x為空或x的val字段為空都說明key沒有對應(yīng)的值
returnnull;
}
returnx.val;
}

//判斷key是否存在在Map中
publicbooleancontainsKey(Stringkey){
returnget(key)!=null;
}

//判斷是和否存在前綴為prefix的鍵
publicbooleanhasKeyWithPrefix(Stringprefix){
//只要能找到一個(gè)節(jié)點(diǎn)，就是存在前綴
returngetNode(root,prefix)!=null;
}

//在所有鍵中尋找query的最短前綴
publicStringshortestPrefixOf(Stringquery){
TrieNodep=root;
//從節(jié)點(diǎn)node開始搜索key
for(inti=0;iif(p==null){
//無法向下搜索
return"";
}
if(p.val!=null){
//找到一個(gè)鍵是query的前綴
returnquery.substring(0,i);
}
//向下搜索
charc=query.charAt(i);
p=p.children[c];
}

if(p!=null&&p.val!=null){
//如果query本身就是一個(gè)鍵
returnquery;
}
return"";
}

//在所有鍵中尋找query的最長前綴
publicStringlongestPrefixOf(Stringquery){
TrieNodep=root;
//記錄前綴的最大長度
intmax_len=0;

//從節(jié)點(diǎn)node開始搜索key
for(inti=0;iif(p==null){
//無法向下搜索
break;
}
if(p.val!=null){
//找到一個(gè)鍵是query的前綴，更新前綴的最大長度
max_len=i;
}
//向下搜索
charc=query.charAt(i);
p=p.children[c];
}

if(p!=null&&p.val!=null){
//如果query本身就是一個(gè)鍵
returnquery;
}
returnquery.substring(0,max_len);
}

//搜索前綴為prefix的所有鍵
publicListkeysWithPrefix(Stringprefix){
Listres=newLinkedList<>();
//找到匹配prefix在Trie樹中的那個(gè)節(jié)點(diǎn)
TrieNodex=getNode(root,prefix);
if(x==null){
returnres;
}
//DFS遍歷以x為根的這棵Trie樹
traverse(x,newStringBuilder(prefix),res);
returnres;
}

//遍歷以node節(jié)點(diǎn)為根的Trie樹，找到所有鍵
privatevoidtraverse(TrieNodenode,StringBuilderpath,Listres){
if(node==null){
//到達(dá)Trie樹底部葉子結(jié)點(diǎn)
return;
}

if(node.val!=null){
//找到一個(gè)key，添加到結(jié)果列表中
res.add(path.toString());
}

//回溯算法遍歷框架
for(charc=0;c//做選擇
path.append(c);
traverse(node.children[c],path,res);
//撤銷選擇
path.deleteCharAt(path.length()-1);
}
}

//通配符.匹配任意字符
publicListkeysWithPattern(Stringpattern){
Listres=newLinkedList<>();
traverse(root,newStringBuilder(),pattern,0,res);
returnres;
}

//遍歷函數(shù)，嘗試在「以node為根的Trie樹中」匹配pattern[i..]
privatevoidtraverse(TrieNodenode,StringBuilderpath,Stringpattern,inti,Listres){
if(node==null){
//樹枝不存在，即匹配失敗
return;
}
if(i==pattern.length()){
//pattern匹配完成
if(node.val!=null){
//如果這個(gè)節(jié)點(diǎn)存儲著val，則找到一個(gè)匹配的鍵
res.add(path.toString());
}
return;
}
charc=pattern.charAt(i);
if(c=='.'){
//pattern[i]是通配符，可以變化成任意字符
//多叉樹（回溯算法）遍歷框架
for(charj=0;j1,res);
path.deleteCharAt(path.length()-1);
}
}else{
//pattern[i]是普通字符c
path.append(c);
traverse(node.children[c],path,pattern,i+1,res);
path.deleteCharAt(path.length()-1);
}
}

//判斷是和否存在前綴為prefix的鍵
publicbooleanhasKeyWithPattern(Stringpattern){
//從root節(jié)點(diǎn)開始匹配pattern[0..]
returnhasKeyWithPattern(root,pattern,0);
}

//函數(shù)定義：從 node 節(jié)點(diǎn)開始匹配 pattern[i..]，返回是否成功匹配
privatebooleanhasKeyWithPattern(TrieNodenode,Stringpattern,inti){
if(node==null){
//樹枝不存在，即匹配失敗
returnfalse;
}
if(i==pattern.length()){
//模式串走到頭了，看看匹配到的是否是一個(gè)鍵
returnnode.val!=null;
}
charc=pattern.charAt(i);
//沒有遇到通配符
if(c!='.'){
//從node.children[c]節(jié)點(diǎn)開始匹配pattern[i+1..]
returnhasKeyWithPattern(node.children[c],pattern,i+1);
}
//遇到通配符
for(intj=0;j//pattern[i]可以變化成任意字符，嘗試所有可能，只要遇到一個(gè)匹配成功就返回
if(hasKeyWithPattern(node.children[j],pattern,i+1)){
returntrue;
}
}
//都沒有匹配
returnfalse;
}

//從節(jié)點(diǎn)node開始搜索key，如果存在返回對應(yīng)節(jié)點(diǎn)，否則返回null
privateTrieNodegetNode(TrieNodenode,Stringkey){
TrieNodep=node;
//從節(jié)點(diǎn)node開始搜索key
for(inti=0;iif(p==null){
//無法向下搜索
returnnull;
}
//向下搜索
charc=key.charAt(i);
p=p.children[c];
}
returnp;
}

publicintsize(){
returnsize;
}
}

接下來我們只要對TrieMap做簡單的封裝，即可實(shí)現(xiàn)TrieSet：

classTrieSet{
//底層用一個(gè)TrieMap，鍵就是TrieSet，值僅僅起到占位的作用
//值的類型可以隨便設(shè)置，我參考Java標(biāo)準(zhǔn)庫設(shè)置成Object
privatefinalTrieMap