所有代码详见：https://github.com/jingminglake/Leetcode
总体思路
前缀树是树结构，特点是其中从根往下走的路径，是有前缀意义的。最常见的是字母前缀树，路径本质是单词和单词的前缀。
- 前缀树和hashtable的关系 相同之处在于，两者都可以对一组信息（例如一个字典，也就是单词集合）进行存储和管理，对hash技术来说就是存储到一张hash表里面，对前缀树来说就是存储成一颗前缀树。且两者查找一个存在的单词都是很快的，那就是只需要平均单词长度的时间。
不同之处在于如果单词不存在于字典中，使用前缀树，这时候前缀树可以让前缀就不符合的直接返回false，反之hash一定会访问单词的每个字母来计算hash。另外，空间上前缀树有时候也比hash空间多（前缀树需要保存边的关系也需要额外空间）。
- 题目特点 （1）一组字符串（单词或者数字的二进制），且需要考虑前缀。遇到这种特点的问题，首先把这组字符串变成一颗字典树。这样做的好处就是，时间复杂度不需要考虑数组的大小，而只与单词的长度有关系。也就是说，思想在于把真正有价值的信息进行浓缩，将计算的空间浓缩为树结构。这样，对树结构进行DFS时候，时间复杂度就是单词的总长度（树结构的边数比结点数小1）。
（2）一组字符串（单词或者数字的二进制），扫描时候，发现当前扫描元素与之前扫描元素全部都有关联，也就是说，对自己要考虑之前的元素，自己计算完后下个元素又要考虑自己。使用trie就是一步步的构建，这样自己就融入了树，对后面元素做出了贡献。
具体题目
208. Implement Trie (Prefix Tree)
题意：实现前缀树。
解：一开始，前缀树只有一个dummy节点作为root。然后将单词一个个的插入到树中。 每个节点采用指针数组指向下一层，使用大小为26的指针数组，数组某个位置例如第一个位置指针如果不为空，那么说明当前层包含a；第二个位置如果不为空，那么说明当前层包含b。
插入操作：沿着root向下，如果当前层该字母存在，则沿着该字母向下，否则，建立一个该字母位置的节点，代表字母下多了一层。单词最后一个字母所在节点的isword标记置为true。
查找单词的最后一个字母所在结点的操作：沿着root向下找，如果找到下一层对应字母为空，那么返回空，否则向下找直到找到最后一层字母的指针返回。
搜索单词是否存在：查找单词的最后一个字母所在层结点指针不为空，且isword标记为true，说明存在。
搜索单词前缀是否存在：查找单词的最后一个字母所在层结点是否为空指针。
建树的过程就是对每个单词字母扫描的过程，总的时间复杂度是O(单词总长度)。
注意：（1）要使用memset来初始化指针数组。（2）要释放内存。
720. Longest Word in Dictionary
题意：给出一个集合，求出集合中单词能够通过每次在最后添加字母来构建的单词中的最长的那个。例如给出集{“w”,”wo”,”wor”,”worl”, “world”}，返回world。如果有多个答案，那么返回字母序最小的那个。
解：暴力法：就是将单词先全部存入hashset，目标单词可能是集合中的任意一个单词，所以进行扫描，对每个单词，看它的子结构（例如对于单词cat，子结构就是{ca，c} ）是否都在hashset中。其中找出子结构，消耗时间O（W^2），所以总时间复杂度是O(∑Wi^2)，其中i是单词下标，W是单词长度。
改进法：单词”world”能否构建递归为{“w”,”wo”,”wor”,”worl”}是否都能被构建,其实也就是”worl”能否被构建，其中”worl”能否被构建取决于{“w”,”wo”,”wor”｝，也就是”wor”是否能都被构建。 这显然是一个存在大量重复子递归的问题。解决方法两种：
（1）自顶向下的解法就是递归加记忆计算过的子问题的结果
推荐。
（2）自底向上就是从最短的单词一步步向最长单词构建
每次构建只需要看去掉最后一个字符的前缀字串是否是可以被构建的，但是这种方法需要先对单词进行从小到大排序。
使用hash表记录可以构建的字符串；判断字符串是否可以被构造的时候，只需要看去掉最后一个字母的子串是否已经在hash中存在了，如果不存在，那么该单词不存入hash表，如果存在就存入。时间复杂度O（NlogN + ∑Wi）。
最优法：使用Trie，构建树花费O(∑Wi)，在DFS遍历一遍，将是单词的进行比较，选出最长的。花费O(∑Wi)。使用DFS，由于每次都从字母序小的进行扫描，因此只要后面的候选者长度不超过之前候选者，就可以不用替换之前的值。
PS. 对单词集合进行基于比较的排序的时间复杂度：单词比较耗时O(L)，L为最大单词长度， 单词比较次数为O(NlogN)，时间复杂度为O(L * N *logN)，由于W往往是常数，所以总的来说，复杂度是O(NlogN)。
212. Word Search II
题意:字母矩阵里面找单词,与79题区别在于，现在是找一组单词。
解：此题如果使用79的方法一个个单词去找，时间复杂度很高。更好的解法是：使用Trie树。先把单词全部转成一棵树，再把树当做一个整体，在矩阵中进行回溯。 两棵树一起遍历，也就是说矩阵遍历时候，有一个明确对应的trietree结点，具体来说也就是当前字符对应结点的父节点，例如一开始是root，后来根据具体字符进入该字符的结点。 注意：每个起点搜索时候，单词可能出现重复的，所以在trietree上做标记，保证一个单词访问一次。 另外，遇到word时候，不能提前终止dfs，因为该单词可能是其他单词的前缀。。
421. Maximum XOR of Two Numbers in an Array
题意：求出数组中最大的异或组合的结果。
解：此题两两计算暴力求解O(n^2)，无法通过测试。优化的解法是位操作，能将复杂度降到O(32n)。 方法一：使用hashset去重。 构造32个mask = 1000…000, 1100…000, 1110…000，然后依次使用这些mask将数组中的每个元素的前i位给取下来。 取下来之后，存到set里面去重，然后构造一个res, 每次置res的第i位是1，前i-1位是每次计算最终的结果，之后是全0，然后与set集合的每个元素进行异或。利用技巧，我们可以知道，如果异或之后的结果仍然出现在集合中，那么说明此组合一定存在。其中不用考虑元素重复的问题，因为一个元素与自己异或是得不出1的。如果该res存在，那么说明当前第i位可以确定为1了，那么继续尝试构造第i-1位。 方法二：使用trietree。 先把所有整数的二进制建立trie树，然后对每个整数沿着前缀树找与全1异或的整数的结点，找到记录为1，否则记录为0，一直往下找，最终记录为一个结果，所有结果中最大的就是要求的数。 具体查找：先计算当前结点的与1异或的值，然后看当其结点是否存在，如果不存在，那么沿着另一条路径走（也就是等于当前结点的路径走，因为接下来仍需要走到叶子结点，因为要找的数一定要存在，而且当前点即使不能异或，但是下一位仍然可以异或，上一位异或不成不影响后续异或）。 这种做法的原理是尝试在trie树中找出某个数字最大的异或数，而Trie树本身就包含了所有其他的数字(也包含自身，但是自己和自己异或起来值为0，不可能是答案)，所以一定可以求出符合条件的数字。然后在找的过程中，树是按照高位在上的，这样，一旦发现与自己异或的数，那么记录当前位为1，最后就得到对于当前数的最大异或值，最终取一个最大值就可以了。 一个优化方法是：一个一个加，一个一个的查，自己加入时候只关心前面存在的，后面新元素加入的时候自然会考虑到之前元素，最终取出一个最小值就好。
