递归方法内的java循环

问题描述：

我有一个名为TrieNode的类，它有一个char键和triNode的arrayList。我正在尝试执行一个trie。递归方法内的java循环

结构：

something like this

例如根密钥是'。孩子们是t，o，s和p。对于具有密钥's'的节点，孩子是t和p。我想计算trie中的节点数。我用这个算法

public int size(TrieNode tmp, int n){ 

    if(tmp.children.isEmpty()){ 
     return 0; 
    } 

    for(int i=0;i<tmp.children.size();i++){ 
     return 1 + size(tmp.children.get(i), n); 
    } 


    return 1; 
}

问题是我对每个电话都不是唯一的。所以这个方法是在根上调用的，然后是孩子t然后是o直到p。当它再次返回时，它不会调用p上的方法。

如何解决这个问题？

你为什么混合递归和循环？ –

，因为我想遍历ArrayList以便在所有节点上调用我的方法。 –

@Aominè为什么他不应该？如果你有一棵树，并且你需要在每个节点上重复出现，我认为可以循环遍历给定节点的所有子节点，并在每个节点上重复出现。 – BackSlash

答

问题是您退出第一个元素的循环。如果你想总结所有的元素，那么你需要在返回父项之前对递归结果进行求和。

public int size(TrieNode tmp, int n){ 

    int sum = 0; 
    for(int i=0;i<tmp.children.size();i++){ 
     sum += size(tmp.children.get(i), n); 
    } 

    if(/* node has char n */){ 
     return sum + 1; 
    } 
    return sum ; 
}

感谢您的帮助。 –

这就是堆栈的用途。递归函数在开始时可能会非常棘手，但它们很容易:) – Beri

答

使用DFS这个算法。您访问的每个节点都是一个子节点。在您访问该子节点之后总结计数。做这样的事情..

//the root is the first node to be passed on.** 
void size(TrieNode node){ 
if(node is null) return; 
if(node is not null) result.add(node); 

while(there exist childNode in node){ 
    size(childNode); 
} 
}

结果是包含树的所有节点的ArrayList。 result.size()为您提供了树中的节点数量。

递归方法内的java循环

相关推荐