一文带你深入了解 Trie 树字典树文章目录一文带你深入了解 Trie 树字典树简单介绍Trie树模板实现 Trie (前缀树)题目字典序的第K小数字实现 Trie (前缀树)总结简单介绍Trie树模板实现 Trie (前缀树)代码如下示例class Trie{private:vectorTrie*children;bool isEnd;Trie*searchPrefix(string prefix){Trie*nodethis;for(charch:prefix){ch-a;if(node-children[ch]nullptr){returnnullptr;}nodenode-children[ch];}returnnode;}public:Trie():children(26),isEnd(false){}voidinsert(string word){Trie*nodethis;for(charch:word){ch-a;if(node-children[ch]nullptr){node-children[ch]newTrie();}nodenode-children[ch];}node-isEndtrue;}boolsearch(string word){Trie*nodethis-searchPrefix(word);returnnode!nullptrnode-isEnd;}boolstartsWith(string prefix){returnthis-searchPrefix(prefix)!nullptr;}};题目字典序的第K小数字代码如下示例class Solution{public:intgetSteps(intcurr,longn){intsteps0;longfirstcurr;// 当前前缀的起始数字比如curr1first初始是1然后是10、100...longlastcurr;// 当前前缀的结束数字比如curr1last初始是1然后是19、199...while(firstn){// 累加当前层的有效数字个数比如n13curr1时第一层是1-11个第二层是10-134个stepsmin(last,n)-first1;firstfirst*10;// 下一层前缀起始1→10→100...lastlast*109;// 下一层前缀结束1→19→199...}returnsteps;}intfindKthNumber(intn,intk){intcurr1;k--;// 因为curr初始是1已经指向第一个数字先把k减1转化为“剩余步数”while(k0){intstepsgetSteps(curr,n);// 计算当前前缀能走的步数if(stepsk){// 步数不够说明目标不在当前前缀的子树里向右走k-steps;// 减去当前前缀的所有步数curr;// 切换到下一个前缀比如从1→2}else{// 步数足够说明目标在当前前缀的子树里向下走currcurr*10;// 进入下一层比如从1→10k--;// 走一步剩余步数减1}}returncurr;// 当k0时curr就是第k小的数字}};// 难啊class Solution{public:intgetStep(intcur,longn){intsteps0;longfirstcur;longlastcur;while(firstn){stepsmin(last,n)-first1;firstfirst*10;lastlast*109;}returnsteps;}intfindKthNumber(intn,intk){intcur1;k--;while(k0){intstepgetStep(cur,n);if(stepk){k-step;cur;}else{curcur*10;k--;}}returncur;}};实现 Trie (前缀树)代码如下示例class Trie{private:vectorTrie*children;bool isEnd;Trie*searchPrefix(string prefix){Trie*nodethis;for(charch:prefix){ch-a;if(node-children[ch]nullptr){returnnullptr;}nodenode-children[ch];}returnnode;}public:Trie():children(26),isEnd(false){}voidinsert(string word){Trie*nodethis;for(charch:word){ch-a;if(node-children[ch]nullptr){node-children[ch]newTrie();}nodenode-children[ch];}node-isEndtrue;}boolsearch(string word){Trie*nodethis-searchPrefix(word);returnnode!nullptrnode-isEnd;}boolstartsWith(string prefix){returnthis-searchPrefix(prefix)!nullptr;}};总结这篇文章是作者搜集大量面经和资料这里出来的。感谢你的支持作者wkm是一名中国矿业大学(北京) 大一的新生希望得到你的关注如果可以的话记得一键三联
一文带你深入了解 Trie 树（字典树）
发布时间：2026/5/19 8:14:09
一文带你深入了解 Trie 树字典树文章目录一文带你深入了解 Trie 树字典树简单介绍Trie树模板实现 Trie (前缀树)题目字典序的第K小数字实现 Trie (前缀树)总结简单介绍Trie树模板实现 Trie (前缀树)代码如下示例class Trie{private:vectorTrie*children;bool isEnd;Trie*searchPrefix(string prefix){Trie*nodethis;for(charch:prefix){ch-a;if(node-children[ch]nullptr){returnnullptr;}nodenode-children[ch];}returnnode;}public:Trie():children(26),isEnd(false){}voidinsert(string word){Trie*nodethis;for(charch:word){ch-a;if(node-children[ch]nullptr){node-children[ch]newTrie();}nodenode-children[ch];}node-isEndtrue;}boolsearch(string word){Trie*nodethis-searchPrefix(word);returnnode!nullptrnode-isEnd;}boolstartsWith(string prefix){returnthis-searchPrefix(prefix)!nullptr;}};题目字典序的第K小数字代码如下示例class Solution{public:intgetSteps(intcurr,longn){intsteps0;longfirstcurr;// 当前前缀的起始数字比如curr1first初始是1然后是10、100...longlastcurr;// 当前前缀的结束数字比如curr1last初始是1然后是19、199...while(firstn){// 累加当前层的有效数字个数比如n13curr1时第一层是1-11个第二层是10-134个stepsmin(last,n)-first1;firstfirst*10;// 下一层前缀起始1→10→100...lastlast*109;// 下一层前缀结束1→19→199...}returnsteps;}intfindKthNumber(intn,intk){intcurr1;k--;// 因为curr初始是1已经指向第一个数字先把k减1转化为“剩余步数”while(k0){intstepsgetSteps(curr,n);// 计算当前前缀能走的步数if(stepsk){// 步数不够说明目标不在当前前缀的子树里向右走k-steps;// 减去当前前缀的所有步数curr;// 切换到下一个前缀比如从1→2}else{// 步数足够说明目标在当前前缀的子树里向下走currcurr*10;// 进入下一层比如从1→10k--;// 走一步剩余步数减1}}returncurr;// 当k0时curr就是第k小的数字}};// 难啊class Solution{public:intgetStep(intcur,longn){intsteps0;longfirstcur;longlastcur;while(firstn){stepsmin(last,n)-first1;firstfirst*10;lastlast*109;}returnsteps;}intfindKthNumber(intn,intk){intcur1;k--;while(k0){intstepgetStep(cur,n);if(stepk){k-step;cur;}else{curcur*10;k--;}}returncur;}};实现 Trie (前缀树)代码如下示例class Trie{private:vectorTrie*children;bool isEnd;Trie*searchPrefix(string prefix){Trie*nodethis;for(charch:prefix){ch-a;if(node-children[ch]nullptr){returnnullptr;}nodenode-children[ch];}returnnode;}public:Trie():children(26),isEnd(false){}voidinsert(string word){Trie*nodethis;for(charch:word){ch-a;if(node-children[ch]nullptr){node-children[ch]newTrie();}nodenode-children[ch];}node-isEndtrue;}boolsearch(string word){Trie*nodethis-searchPrefix(word);returnnode!nullptrnode-isEnd;}boolstartsWith(string prefix){returnthis-searchPrefix(prefix)!nullptr;}};总结这篇文章是作者搜集大量面经和资料这里出来的。感谢你的支持作者wkm是一名中国矿业大学(北京) 大一的新生希望得到你的关注如果可以的话记得一键三联
