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& 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