hot100实现Trie前缀树
目录
【hot100】实现Trie（前缀树）
一、思路
这题的思路很简单，其实就是一个26叉树，但是这个数不同通过通常的左右节点属性，而是一个数组来存储的，每个数组下标存储下层的数组。其中有以下需要注意的点：
1.private Trie[] children;
这个说明孩子节点是一个Trie类型的数组，即数组中每个下标存储的就是一个Trie结构类型，每个下标包含两个属性，即可以通过Trie.children[index]访问到子节点，Trie.children[index].isEnd访问到子节点的isEnd属性。
2.递归数据结构VS递归函数
以下是递归数据结构的核心代码，可以明显的看出和普通函数调用式递归的区别
还有就是其中通过’this’来获取根类
public void insert(String word){
Trie node = this;//获取当前类，赋值给node
for (int i =0;i<word.length();i++){
char letter = word.charAt(i);
int num = letter - 'a';//获取当前字符相对于a的位置
//注意下面代码都是对当前层的node进行操作，不要直接引用类属性，不然就是在反复修改根节点了
if (node.children[num]==null){//当前字母对应的数组为空
node.children[num]=new Trie();//使用上面构造的初始化函数，向下赋值；
}
node = node.children[num];
}
node.isEnd = true;
}1. 递归结构本质
数据结构的递归性 ：
Trie 树的每个节点（
Trie对象）包含一个子节点数组children，每个子节点又是一个Trie实例。这种结构天然形成一棵多叉树，通过 对象间的引用关系 隐式构建递归层级。操作逻辑的非递归性 ：
代码中通过 循环迭代 （如
for循环）遍历树的层级，而非显式调用自身方法。例如，insert方法通过移动node指针（node = node.children[num]）逐层向下插入节点。迭代代替递归 ：
通过
node指针的更新模拟递归的层级深入，但未发生函数调用栈的变化。2. 优点
- 内存高效 ：避免函数递归调用的栈开销，适合处理深度较大的数据结构。
- 性能稳定 ：无栈溢出风险，适合处理长字符串或大规模数据。
- 逻辑直观 ：通过对象引用直接操作树形结构，代码可读性高
特性 递归数据结构 递归函数 核心体现 数据结构中包含对自身类型的引用 函数调用自身 操作方式 通常使用迭代（如循环）操作对象引用 显式调用自身，通过调用栈保存状态 内存消耗 低（无栈帧累积） 高（每层递归产生栈帧，可能栈溢出） 适用场景 树形结构（如 Trie、二叉树）、链表等 分治、回溯、树/图遍历等 代码示例 Trie[] children（Trie 树）void preOrder(TreeNode node)（二叉树遍历）
二、记忆
1.多叉树用数组表示
2.递归数据结构的使用
3.字符相减获取相对位置
int num = letter - ‘a’;//获取当前字符相对于a的位置
三、代码
public class Trie{
private Trie[] children;
private boolean isEnd;
public Trie(){
children = new Trie[26];
isEnd = false;
}
public void insert(String word){
Trie node = this;//获取当前类，赋值给node
for (int i =0;i<word.length();i++){
char letter = word.charAt(i);
int num = letter - 'a';//获取当前字符相对于a的位置
//注意下面代码都是对当前层的node进行操作，不要直接引用类属性，不然就是在反复修改根节点了
if (node.children[num]==null){//当前字母对应的数组为空
node.children[num]=new Trie();//使用上面构造的初始化函数，向下赋值；
}
node = node.children[num];
}
node.isEnd = true;
}
public boolean search(String word){
Trie trie = searchPrefix(word);
return trie!=null && trie.isEnd;//和搜索前缀唯一的不同就是要求当前节点是结束节点
}
public boolean startsWith(String prefix){
return searchPrefix(prefix)!=null;
}
private Trie searchPrefix(String word){
Trie node = this;
for (int i =0;i<word.length();i++){
char letter = word.charAt(i);
int num = letter - 'a';//获取当前字符相对于a的位置
if (node.children[num]==null){//当前字母对应的数组为空
return null;
}
node = node.children[num];
}
return node;
}
}