Trie树叶子节点统计异常：计数变量始终重置为0求解决

你遇到的问题根源在于使用了**成员变量num**来统计叶子节点数。每个Trie节点实例都有自己的num成员，当你递归调用node.countLeafNodes()时，操作的是子节点自己的num，而不是根节点的num——最终根节点返回的num只会统计它直接子节点中标记为单词的节点，深层子树的叶子节点数根本没累加到根节点的计数里。而且如果多次调用countLeafNodes()，num还会因为没有重置而出现错误的累加值。

我们应该把计数逻辑改成递归返回累加值，用局部变量维护当前子树的叶子数，避免成员变量带来的上下文混乱。修改后的代码如下：

public int countLeafNodes() {
    int num = 0;
    // 如果当前节点本身是一个单词（叶子节点），计数加1
    if (this.isWord) {
        num++;
    }
    // 递归遍历所有子节点，累加它们的叶子节点数
    for (char c : children.keySet()) {
        Trie node = children.get(c);
        num += node.countLeafNodes();
    }
    return num;
}

• 每次递归调用都会创建一个局部的num变量，专门统计当前子树的叶子节点数，不会和其他节点的计数混淆。
• 当前节点如果是单词（即完整单词的结束节点），先给自己加1。
• 遍历所有子节点，把每个子节点返回的叶子数累加到当前的num里，最后返回这个累加值。这样从最底层的节点开始往上累加，最终根节点就能得到整个Trie树的总叶子数。

如果你的isWord标记的是单词的结束，但存在单词是另一个单词前缀的情况（比如"app"和"apple"），那"app"对应的节点虽然isWord=true，但它不是真正的叶子节点（因为有子节点）。这时候你需要调整判断逻辑，只统计是单词且没有子节点的节点：

public int countLeafNodes() {
    int num = 0;
    // 只有当是单词且没有子节点时，才是真正的叶子节点
    if (this.isWord && this.children.isEmpty()) {
        num++;
    }
    for (char c : children.keySet()) {
        Trie node = children.get(c);
        num += node.countLeafNodes();
    }
    return num;
}

这样就能准确统计Trie树中真正的叶子节点了。

内容的提问来源于stack exchange，提问作者thiuye