trie节点中的节点数

Question

在这里，我创建了一个类Trie和TrieNode，它在Java中实现了Trie数据结构。我有一个任务要写一个名为size(([return type int]的方法来返回Trie中的节点数。

class Trie {
private TrieNode root;
/////////////////////
// TrieNode class
class TrieNode {
public char c;
public boolean isWord;
public TrieNode[] children;
public TrieNode(char c) {
this.c = c;
isWord = false;
children = new TrieNode[26];
}
}
public Trie() {
root = new TrieNode('');
}
public boolean isPrefix(String word) {
return getNode(word) != null;
}
public void insert(String word) {
TrieNode curr = root;
for (int i = 0; i < word.length(); i++) {
char c = word.charAt(i);
if (curr.children[c - 'A'] == null)
curr.children[c - 'A'] = new TrieNode(c);
curr = curr.children[c - 'A'];
}
curr.isWord = true;
}
// Helper
private TrieNode getNode(String word) {
TrieNode curr = root;
for (int i = 0; i < word.length(); i++) {
char c = word.charAt(i);
if (curr.children[c - 'A'] == null)
return null;
curr = curr.children[c - 'A'];
}
return curr;
}

我一直在尝试获取Trie中的节点数量，我想的是：

public int size() {
return size(root);
}
private int size(TrieNode root) {
for (int i = 0; i < root.children.length; i++) {
if (root.children[i] != null) {
if (root.isWord)
return 1;
else
return 1 + size(root.children[i]);
}
}
return 0;
}

但这是不对的。有什么想法吗？

Answer 1

这是一个简单的深度优先搜索：

public static int size(TrieNode node) {
if(node == null)
return 0;

int total = 1;

for(TreeNode child : node.children)
total += size(child);

return total;
}