C++에서 n-ary 트리의 짝수 크기 하위 트리

이 문제에서는 n-ary 트리를 나타내는 인접 목록이 제공됩니다. 우리의 임무는 n-ary 트리에서 짝수 크기의 하위 트리의 수를 찾는 것입니다.

N-ary 트리 은 일반적으로 다음과 같은 방식으로 계층적으로 표현되는 노드 모음으로 정의됩니다.

트리는 루트 노드에서 시작됩니다.

트리의 각 노드는 하위 노드에 대한 포인터 목록을 유지 관리합니다.

하위 노드의 수가 m보다 작거나 같습니다.

문제를 이해하기 위해 예를 들어 보겠습니다.

입력:

<강한>

출력: 4

설명:

뿌리가 7인 나무는 크기가 짝수입니다.
2로 뿌리를 내린 나무는 크기가 짝수입니다.
뿌리가 0인 트리는 크기가 짝수입니다.
뿌리가 3인 나무는 크기가 짝수입니다.

해결 방법 -

간단한 접근 방식은 주어진 노드에 대한 모든 자식 노드를 계산하는 것입니다(eventTreeCount가 증가하더라도). 이를 위해 DFS를 사용하고 주어진 노드에 대한 SubTree의 길이를 찾습니다.

트리에서 단일 순회를 사용하여 이를 수행할 수 있습니다. 재귀적으로 각 자식 노드의 하위 트리 크기를 찾은 다음 크기를 확인하고 짝수이면 eventTreeCount를 늘리고 그렇지 않으면 그대로 둡니다.

우리 솔루션의 작동을 설명하는 프로그램,

예시

#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