• 这个问题曾经在美团二面的时候，面试官问场景题考察过，但是当时并不知道面试官考察的知识点

字典树：

是一种树形结构，典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串,如01字典树）。主要思想是利用字符串的公共前缀来节约存储空间。很好地利用了串的公共前缀，节约了存储空间。字典树主要包含两种操作，插入和查找。

字典树的优点：

1. 节约空间

2. 快速检索

比如我们在储存url的时候，最常见的就是 https://www 这种形式的，这种格式的网址，在字典树中，只需要11个字符即可储存下来，对于相同的前缀的网址，可以归为树的一个分支中去。这样查找的时候，也非常的方便，按照单词字母顺序直接依层查找即可。

字典树需要满足的条件：

我们需要将一个单词列表建出一棵单词查找树，满足：

• 根结点不包含字母，除根结点外的每个都仅含一个大写英文字母；
• 从根结点到某一节点，路径上经过的字母依次连起来所构成的单词，称为该结点对应的单词。单词列表中的每个词，都是该单词查找树某个结点所对应的单词；
• 在满足上述条件下，该单词查找树的结点数最少，统计出该单词查找树的结点数目。

2021-6-21 字典树（前缀树）

原文：https://www.cnblogs.com/jobshenlei/p/14912324.html