特里树的高度（层数）

Question

我有一个 trie，其中每个节点都是一个对象 TrieNode，如下所示：

public char content; 
public double count;
public LinkedList<TrieNode> childList;

我必须计算 trie 的高度（root 的级别 = 0）。

这就是我所做的：

int levels = getLevels(getRoot());
System.out.println("levels: " + levels);

public int getLevels(TrieNode node) {
    int lev = 0;
    if(node != null) {
        TrieNode current = node;  
        for(TrieNode child : node.childList) {
            lev += getLevels(child);
        }      
    }   
    return lev;
}

但它 returns 总是 0。为什么？谢谢

Answer 1

下降到 children 时需要加 1，否则 lev 没有任何值 non-zero。

请注意，您在此代码中不是计算 the height of the trie，而是对路径的长度求和。您需要找到最大路径长度：

int lev = 1;
for (TrieNode child : node.childList) {
  lev = Math.max(lev, 1 + getLevels(child));
}

特里树的高度（层数）

Height of a trie (number of levels)

java

trie

levels