考虑一棵拥有 26 个子节点指针的树，用边来代表字母，而从根结点到树上某一结点的路径就代表了一个字符串。在这棵树上，还需要一个布尔型变量，表示以当前节点作为结束的串是否存在。

Trie 最基本的应用就是存储和查询字符串是否存在。

例题 1：力扣 208. 实现 Trie (前缀树)

遵循力扣风格，用类来实现，代码：

参考代码
  1. struct Node {
  2.     bool val = false;
  3.     Node* next[26] = {NULL};
  4. };
  6. class Trie {
  7. public:
  8.     Node* root;
  9.     /** Initialize your data structure here. */
  10.     Trie() {
  11.         root = new Node();
  12.     }
  14.     /** Inserts a word into the trie. */
  15.     void insert(string word) {
  16.         int n = word.length();
  17.         Node* p = root;
  18.         for (int i=0; i<n; ++i) {
  19.             char cur = word[i];
  20.             if (p->next[cur - 'a'] != nullptr) {
  21.                 p = p->next[cur - 'a'];
  22.             } else {
  23.                 p->next[cur - 'a'] = new Node();
  24.                 p = p->next[cur - 'a'];
  25.             }
  26.         }
  27.         p->val = true;
  28.     }
  30.     /** Returns if the word is in the trie. */
  31.     bool search(string word) {
  32.         int n = word.length();
  33.         Node* p = root;
  34.         for (int i=0; i<n; ++i) {
  35.             char cur = word[i];
  36.             if (p->next[cur - 'a'] != nullptr) {
  37.                 p = p->next[cur - 'a'];
  38.             } else {
  39.                 return false;
  40.             }
  41.         }
  42.         return p->val;
  43.     }
  45.     /** Returns if there is any word in the trie that starts with the given prefix. */
  46.     bool startsWith(string prefix) {
  47.         int n = prefix.length();
  48.         Node* p = root;
  49.         for (int i=0; i<n; ++i) {
  50.             char cur = prefix[i];
  51.             if (p->next[cur - 'a'] != nullptr) {
  52.                 p = p->next[cur - 'a'];
  53.             } else {
  54.                 return false;
  55.             }
  56.         }
  57.         return true;
  58.     }
  59. };
  61. /**
  62.  * Your Trie object will be instantiated and called as such:
  63.  * Trie* obj = new Trie();
  64.  * obj->insert(word);
  65.  * bool param_2 = obj->search(word);
  66.  * bool param_3 = obj->startsWith(prefix);
  67.  */

本数据结构的逻辑比较简单，你也可以尝试写出符合自己逻辑的版本。

例题 2：力扣 421. 数组中两个数的最大异或值

Trie 的另一个应用，和异或有关，你可能需要先行熟悉「位运算」相关知识。将数的二进制表示看做一个字符串，就可以建出字符集为 5.11.2 Trie 字典树 * - 图1 的 Trie 树。

题解请参考官方题解的字典树方法。

参考代码：
  1. class Trie {
  2. private:
  3.     const int kMaxBits = 31;
  4.     Trie* next[2] = {nullptr};
  5. public:
  6.     void add(int x) {
  7.         Trie* p = this;
  8.         for (int i = kMaxBits - 1; i >= 0; --i) {
  9.             bool bit = x >> i & 1;
  10.             if (p->next[bit] == nullptr) {
  11.                 p->next[bit] = new Trie();
  12.             }
  13.             p = p->next[bit];
  14.         }
  15.     }
  16.     int match(int x) {
  17.         int ans = 0;
  18.         Trie* p = this;
  19.         for (int i = kMaxBits - 1; i >= 0; --i) {
  20.             bool bit = x >> i & 1;
  21.             ans <<= 1;
  22.             if (p->next[!bit] != nullptr) {
  23.                 ++ans;
  24.                 p = p->next[!bit];
  25.             } else {
  26.                 p = p->next[bit];
  27.             }
  28.         }
  29.         return ans;
  30.     }
  31. };
  32. class Solution {
  33. public:
  34.     int findMaximumXOR(vector<int>& nums) {
  35.         int n = nums.size();
  36.         Trie t;
  37.         int ans = 0;
  38.         for (int i=1; i<n; ++i) {
  39.             t.add(nums[i - 1]);
  40.             ans = max(ans, t.match(nums[i]));
  41.         }
  42.         return ans;
  43.     }
  44. };

拓展练习（难度较高）：AcWing 3485. 最大异或和

原创题解：题解：AcWing 3485. 最大异或和