แผนผังขนาดแม้แต่ในทรี n-ary ใน C++

ในปัญหานี้ เราได้รับรายการที่อยู่ติดกันซึ่งแสดงถึงต้นไม้ n-ary งานของเราคือการหาจำนวนของทรีย่อยขนาดคู่ ในทรี n-ary

ต้นไม้นารี ถูกกำหนดให้เป็นชุดของโหนดที่ปกติจะแสดงตามลำดับชั้นในลักษณะต่อไปนี้

ต้นไม้เริ่มต้นที่โหนดราก

แต่ละโหนดของแผนผังจะเก็บรักษารายการตัวชี้ไปยังโหนดย่อย

จำนวนโหนดย่อยน้อยกว่าหรือเท่ากับ m

มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน

ป้อนข้อมูล:

ผลลัพธ์: 4

คำอธิบาย:

ต้นไม้ที่รูทด้วย 7 มีขนาดเท่ากัน
ต้นไม้ที่หยั่งรากด้วย 2 มีขนาดเท่ากัน
ต้นไม้ที่รูทด้วย 0 จะมีขนาดเท่ากัน
ต้นไม้ที่รูทด้วย 3 ตัวจะมีขนาดเท่ากัน

แนวทางการแก้ปัญหา -

วิธีง่ายๆ คือการนับโหนดย่อยทั้งหมดสำหรับโหนดที่กำหนด หากเป็นการเพิ่มจำนวนevenTreeCount สำหรับสิ่งนี้ เราจะใช้ DFS และค้นหาความยาวของ SubTree สำหรับโหนดที่กำหนด

เราสามารถทำได้โดยใช้ การข้ามผ่านต้นไม้เพียงครั้งเดียว โดยการค้นหาขนาดของทรีย่อยของโหนดย่อยแต่ละโหนดซ้ำแล้วซ้ำอีก จากนั้นตรวจสอบขนาดและถ้าเป็นขนาดเท่ากัน ให้เพิ่ม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