C++のn-aryツリーの偶数サイズのサブツリー

この問題では、n-aryツリーを示す隣接リストが与えられます。私たちのタスクは、n-aryツリー内の偶数サイズのサブツリーの数を見つけることです。

N-aryツリー は、通常、次のように階層的に表されるノードのコレクションとして定義されます。

ツリーはルートノードで開始されます。

ツリーの各ノードは、その子ノードへのポインタのリストを維持します。

子ノードの数がm以下です。

問題を理解するために例を見てみましょう

入力：

出力： 4

説明：

7をルートとするツリーのサイズは同じです。
2をルートとするツリーのサイズは同じです。
0をルートとするツリーは、サイズが均等です。
3をルートとするツリーのサイズは同じです。

ソリューションアプローチ-

単純なアプローチは、evenTreeCountを増やしても、特定のノードのすべての子ノードをカウントすることです。このために、DFSを使用して、指定されたノードのサブツリーの長さを見つけます。

これは、ツリー上の単一のトラバーサルを使用して実行できます。 各子ノードのサブツリーのサイズを再帰的に見つけてサイズを確認し、偶数の場合はevenTreeCountを増やし、それ以外の場合はそのままにします。

ソリューションの動作を説明するプログラム

例

#include <bits/stdc++.h>
using namespace std;

int countEventSizeSubTree(vector<int> adj[], int n, int v, int&amp; EvenCount){

   int size = 1;
   for (auto ele : adj[v]) {
      size += countEventSizeSubTree(adj, n, ele, EvenCount);
   }
   if (size % 2 == 0)
      EvenCount++;
   return size;
}

int main(){

   int n;
   n = 10;

   vector<int> adj[n + 1];
   adj[7].push_back(2);
   adj[7].push_back(9);
   adj[2].push_back(0);
   adj[2].push_back(1);
   adj[9].push_back(3);
   adj[3].push_back(8);
   adj[0].push_back(5);

   int EvenCount = 0;
   countEventSizeSubTree(adj, n, 1, EvenCount);
   cout<<"Even Size SubTree are "<<EvenCount;
   return 0;
}

出力-

Even Size SubTree are 0