C++ में ट्री नोड्स डिलीट करें

मान लीजिए हमारे पास एक ट्री है, यह ट्री नोड 0 पर रूटेड है, यह निम्नानुसार दिया गया है -

1. नोड्स की संख्या nodes है
2. i-वें नोड का मान value[i] है
3. i-वें नोड का पैरेंट parent[i] है

हमें हर उस सबट्री को हटाना है जिसके नोड्स के मानों का योग 0 है, ऐसा करने के बाद ट्री में शेष नोड्स की संख्या लौटाएं। यदि ट्री इस प्रकार है -

7 नोड्स हैं, आउटपुट 2 होगा।

इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे -

• children नामक एक मैप बनाएं
• dfs() नामक एक मेथड परिभाषित करें, जो नोड, एक ऐरे value और ग्राफ लेगा
• temp := एक पेयर (value[node], 1)
• i के लिए 0 से graph[node] के आकार तक की रेंज में
  • temp2 := dfs(graph[node, i], value, graph)
  • फर्स्ट को temp2 के फर्स्ट से बढ़ाएं, सेकंड को temp2 के सेकंड से बढ़ाएं
• यदि temp का फर्स्ट 0 है, तो ans := ans - temp का सेकंड, temp का सेकंड := 0 सेट करें
• temp लौटाएं
• मेन मेथड से, यह nodes, पैरेंट्स ऐरे और वैल्यूज़ ऐरे लेगा
• n := वैल्यूज़ ऐरे में मौजूद वैल्यूज़ की संख्या
• ans := n
• ग्राफ नामक n + 1 आकार का एक ऐरे परिभाषित करें
• i के लिए 1 से n - 1 तक की रेंज में
  • i को graph[parent[i]] में डालें
• dfs(0, value, graph)
• ans लौटाएं

उदाहरण (C++)

बेहतर समझ के लिए निम्नलिखित इम्प्लीमेंटेशन देखें -

#include <bits/stdc++.h> using namespace std; class Solution { public:    map <int, int> children;    int ans;    pair <int, int> dfs(int node, vector<int>& value, vector <int> graph[]){       pair <int, int> temp = {value[node], 1};       for(int i = 0; i < graph[node].size(); i++){          pair <int, int> temp2 = dfs(graph[node][i], value, graph);          temp.first += temp2.first;          temp.second += temp2.second;       }       if(temp.first == 0){          ans -= temp.second;          temp.second = 0;       }       return temp;    }    int deleteTreeNodes(int nodes, vector<int>& parent, vector<int>& value) {       int n = value.size();       ans = n;       children.clear();       vector < int > graph[n + 1];       for(int i = 1; i < n; i++){          graph[parent[i]].push_back(i);       }       dfs(0, value, graph);       return ans;    } }; main(){    vector<int> v1 = {-1,0,0,1,2,2,2};    vector<int> v2 = {1,-2,4,0,-2,-1,-1};    Solution ob;    cout << (ob.deleteTreeNodes(7,v1, v2)); }

इनपुट

7 [-1,0,0,1,2,2,2] [1,-2,4,0,-2,-1,-1]

आउटपुट

2