如何找到trie中最长的单词？

I'm having trouble understanding the concept of a trie. From the "trie" wikipedia entry I have this picture:

如果我正确地看到这一点，trie 中的所有叶节点都将拼写出整个单词，并且所有父节点都保存导致最终叶节点的字符。所以，如果我有一个名为 DigitalTreeNode 定义的类

public class DigitalTreeNode {
       public boolean isAWord;
       public String wordToHere; (compiles all the characters in a word together)
       public Map<String, DTN> children;
}

如果我想实现一个返回 trie 中最长单词的方法，是否只需要在每个叶节点查找最长单词？我将如何实现这样的方法：

public static String longestWord (DigitalTreeNode d);

我猜它涉及设置一个最长的字符串变量，递归地遍历每个节点并检查它是否是一个单词，如果它是一个单词并且它的长度大于最长的变量，则longest = newWordLength。但是，我不确定 Map 子项如何适应。我如何使用上面的方法找到任何 trie 中最长的单词？

叶节点通常不包含整个字符串（尽管可以），很多时候在 trie 中，叶节点只包含一个“$”符号来指示这是字符串的结尾。

要查找 trie 中最长的单词，您可以使用BFS http://en.wikipedia.org/wiki/Breadth-first_search在树上，首先找到“最后”一片叶子。 “最后一个叶子”是从 BFS 队列中弹出的最后一个元素（弹出后，BFS 算法以空队列停止）。
要从这片叶子中获取实际的单词，您需要从叶子回到根。这个线程 https://stackoverflow.com/questions/9590299/how-can-i-find-the-actual-path-found-by-bfs讨论了如何做到这一点。

这个解决方案是O(|S| * n), where |S|是字符串的平均长度，并且n是 DS 中的字符串数。

如果你可以操纵trie DS，我认为它可以做得更好（但这似乎不是这个问题的问题）

伪代码：

findLongest(trie):
  //first do a BFS and find the "last node"
  queue <- []
  queue.add(trie.root)
  last <- nil
  map <- empty map
  while (not queue.empty()):
     curr <- queue.pop()
     for each son of curr:
        queue.add(son)
        map.put(son,curr) //marking curr as the parent of son
     last <- curr
  //in here, last indicate the leaf of the longest word
  //Now, go up the trie and find the actual path/string
  curr <- last
  str = ""
  while (curr != nil):
      str = curr + str //we go from end to start   
      curr = map.get(curr)
  return str