再帰的メソッド内のjava-loop

Question

私は、triNodeのcharキーとarrayListを持つTrieNodeというクラスを持っています。私はトライを実装しようとしています。

構造：例えば

ルートキーがあります ''子供たちはt、o、s、pです。キー 's'を持つノードの場合、子はtとpです。私はトライのノードの数を計算したい。私はこのアルゴリズムを使用しました

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に続いてtに続いてpまで呼び出されます。それが再びsに戻るとき、pのメソッドを呼び出さない。

これを修正するにはどうすればよいですか？

Answer 1

問題は、最初の要素のループを終了することです。すべての要素を合計する場合は、親に返す前に再帰結果を合計する必要があります。このアルゴリズムのための

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 ; 
} 

Answer 2

使用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()は、ツリー内のノードの数を示します。