前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补全和拼写检查

怎么实现的呢？
其实就是一个多叉树，这个多叉树的最大分支就是26（26个字母）

多叉树的数据结构就如下

ps：今天发现的点，在Java中，数组的元素在创建时会被初始化为该元素类型的默认值。对于对象类型（如Node），默认值是null。并且创建对象数组时，构造函数不会被循环调用。数组中的每个元素会被初始化为该类型的默认值（对于对象类型是null），只有在你显式创建每个对象实例时，构造函数才会被调用！！！

class Node{
    Node[] children;
    public Node(){
        children = new Node[26];
    }
}

对比二叉树

class Node{
    Node left_children;
    Node right_children;
    ...
}

在本题对于每一个节点，还有一个关键的成员变量为isEnd，所以这颗前缀树的单个节点结构如下

class Node{
    Node[] children;
    boolean isEnd;

    public Node(){
        children = new Node[26];
        isEnd = false;
    }
}

为什么需要这个isEnd成员变量？

这个就是前缀树高效存储的核心，用isEnd来标记这个节点是不是一个单词的结尾，这样就可以实现重复利用，如图所示，apple和app可以公用一条路径，只需要在结尾标记好true就可以分辨结果

前缀树.png