題目描述：
Implement Trie (Prefix Tree)
Implement a trie with insert, search, and startsWith methods.
Note:
You may assume that all inputs are consist of lowercase letters a-z.
思路：
1.由于題目可以假設(shè)所有input均為小寫字母，因此每個(gè)節(jié)點(diǎn)存1個(gè)字符，
LeetCode Implement Trie (Prefix Tree)
。2.root的val保持空
3.創(chuàng)建樹時(shí)，不斷拿去當(dāng)前word[i]的字符,i∈[0,n)，如果word[i]在當(dāng)前node的children中找不到，就添加到children中。同時(shí)把最后一個(gè)節(jié)點(diǎn)標(biāo)記（hasWord）為是否為單詞的末尾。
4.搜索時(shí)，每次拿word[i]的字符，逐層判斷即可。如果是Search，判斷最后到達(dá)的字符是否標(biāo)記為hasWord；如果僅僅搜索prefix，只需判斷i是否到word結(jié)尾即可。
實(shí)現(xiàn)代碼：
public class TrieNode { // Initialize your data structure here. public TrieNode() { children = new List<trienode>(); hasWord = false; } public TrieNode(char v){ val = v; children = new List<trienode>(); hasWord = false; } public IList<trienode>children; public char val; public bool hasWord ;}public class Trie { public TrieNode root; public Trie() { root = new TrieNode(); } // Inserts a word into the trie. public void Insert(String word) { if(string.IsNullOrEmpty(word)){ return; } var n = root; var index = 0; // try find while(n.children.Count > 0 && index < word.Length){ var first = n.children.FirstOrDefault(x=>x.val == word[index]); if(first != null){ n = first; index++; } else{ break; } } if(index < word.Length){ // if not exist , create new node for(var i = index; i < word.Length; i++){ var child = new TrieNode(word[i]); n.children.Add(child); n = child; } } n.hasWord = true; } // Returns if the word is in the trie. public bool Search(string word) { TrieNode n = null; var index = TryFindNode(word, out n); return index == word.Length && n.hasWord; } // Returns if there is any word in the trie // that starts with the given prefix. public bool StartsWith(string word) { TrieNode n = null; var index = TryFindNode(word, out n); return index == word.Length; } private int TryFindNode(string word, out TrieNode node){ var n = root; var index = 0; while(n.children.Count > 0 && index < word.Length){ var first = n.children.FirstOrDefault(x => x.val == word[index]); if(first != null){ n = first; index++; } else{ break; } } node = n;; return index; }}</trienode></trienode></trienode>