題目描述：

    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>