深さの最初の検索：特定の特性を持つノードの数をカウントしようとしています（java）

Question

私はいくつかのノードが特定の特性を持つツリーを持っています。 DFSのようなアルゴリズムを使って、この特性を持つツリー内のノードの数を数えたいと思います。しかし、私は間違って戻り値を使用しています。この特性を持つノードが見つかった場合は、何らかの種類のカウンタをインクリメントする必要があります。そうでなければ、カウンタはインクリメントしません。

これは非常に簡単ですが、正しく実装できませんでした。

private int dfs(Node node) { 

    for(Node n: node.children){ 
     if(n != null && n.someOtherCondition){ 
      return 1 + dfs(n); 
     } 
    } 
    return 0; 
    } 

Answer 1

一致するノードが見つかったら直ちに戻りません。カウントして最後に戻ります。

private int dfs(Node node) { 
    int count = 0; 
    for(Node n: node.children){ 
    if(n != null && n.someOtherCondition){ 
     count += 1;  // Count this node. 
     count += dfs(n); // Count this node's children. 

     // Alternatively: count += 1 + dfs(n); split up for clarity. 
    } 
    } 
    return count; 
} 

ことが条件に一致した場合、あなたが実際に、あなたから開始ノードをカウントされませんので、あなたが実際に、パラメータnode上の状態を確認していないノート。アプリケーションに応じて、これは必要な場合としない場合があります。

private int dfs(Node node) { 
    if (node == null) return 0; 

    int count = node.someOtherCondition ? 1 : 0; 

    for(Node n: node.children){ 
    count += dfs(n); 
    } 

    return count; 
} 

Answer 2

あなたは再帰的にすべて子供にDFSを呼び出す代わりに、最初の1に返すの結果を蓄積する必要があります：あなたは、実際に、あまりにも、このノードをカウントします。

Answer 3

private int dfs(Node node) { 
    int count = 0; 

    for(Node n: node.children){ 
    if(n != null && n.someOtherCondition){ 
     // check if the child-node has children 
     if(n.children.length > 0){ 
      count = count + dfs(n); // recursively count the grandchildren aswell 
     } 
     count = count + 1; // add one because we meet the condition once on this level 
    } 
    } 

    return count; 
} 

Answer 4

ショートと甘い：

private int dfs(Node node) { 
    int count = node.someOtherCondition ? 1 : 0; 
    for (Node child : node.children) 
     if (child != null) 
      count += dfs(node); 
    return count; 
}