【二叉树】208. 实现 Trie (前缀树)

本文主要是介绍【二叉树】208. 实现 Trie (前缀树)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

208. 实现 Trie (前缀树)

解题思路

Node类：每个Node节点代表Trie树中的一个字符节点。它包含一个字符值val（虽然在这个实现中未直接使用），一个指向子节点的数组child，和一个布尔值end，表示该节点是否为某个单词的结尾。
child数组有26个元素，对应26个小写英文字母，用于存储当前节点的子节点。
end标志用来表示当前节点是否是某个单词的最后一个字符。
Trie类：代表整个前缀树，包含一个根节点root。
insert(String word)方法用于向Trie树中插入一个新单词。它逐字符检查给定单词，如果当前字符在树中没有对应的子节点，则创建一个新的子节点。
search(String word)方法用于检查一个单词是否完整地存在于Trie树中。它按照单词的字符来遍历树，如果能够遍历完整个单词且最后一个字符节点的end为true，则表示单词存在。
startsWith(String prefix)方法用于检查Trie树中是否存在以给定前缀开始的任何单词。这个方法与search方法类似，但它只需要找到前缀即可，不需要验证最后一个字符的end值。

class Trie {private class Node{char val;Node[] child;boolean end;// 表示当前节点是不是一个单词的结尾// 构造函数public Node(char ch){val = ch;child = new Node[26];// 新建一个孩子节点end = false;}public Node(){child = new Node[26];end = false;}}Node root;public Trie() {root = new Node();// 创建根节点}public void insert(String word) {Node cur = root;for(int i = 0; i < word.length(); i++){// 取出当前字符char ch = word.charAt(i);if(cur.child[ch - 'a'] == null){// 当前节点的孩子节点为空节点  将当前字符插入cur.child[ch - 'a'] = new Node(ch);}// 更新当前节点curcur = cur.child[ch - 'a'];}cur.end = true;// 如果一个单词的所有字符全部添加完毕  标记为true}public boolean search(String word) {Node cur = root;// 从根节点开始搜索  和插入的逻辑一样for(int i = 0; i < word.length(); i++){char ch = word.charAt(i);if(cur.child[ch - 'a'] == null){return false;//没有孩子节点}cur = cur.child[ch - 'a'];}return cur.end;}// 寻找是不是又该前缀字符串public boolean startsWith(String prefix) {Node cur = root;for(int i =0; i < prefix.length(); i++){char ch = prefix.charAt(i);if(cur.child[ch - 'a'] == null){return false;}cur = cur.child[ch - 'a'];}return true;}
}/*** Your Trie object will be instantiated and called as such:* Trie obj = new Trie();* obj.insert(word);* boolean param_2 = obj.search(word);* boolean param_3 = obj.startsWith(prefix);*/