C++ में ट्री नोड्स हटाएं

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

1. नोड्स की संख्या नोड्स है
2. ith नोड का मान मान है[i]
3. ith नोड का जनक माता-पिता है[i]

हमें प्रत्येक सबट्री को हटाना होगा जिसका नोड्स के मानों का योग 0 है, ऐसा करने के बाद पेड़ में शेष नोड्स की संख्या वापस कर दें। तो अगर पेड़ जैसा है -

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

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

• बच्चों के नाम से एक नक्शा बनाएं
• डीएफएस () नामक एक विधि को परिभाषित करें, यह नोड, एक सरणी मान और ग्राफ लेगा
• अस्थायी:=एक जोड़ी (मान [नोड], 1)
• मैं के लिए 0 से ग्राफ़ के आकार के बीच [नोड]
  • temp2:=dfs(ग्राफ[नोड, i], मान, ग्राफ)
  • temp2 के पहले से पहले बढ़ाएं, दूसरे temp2 से दूसरे बढ़ाएं
• यदि पहला अस्थायी 0 है, तो उत्तर:=उत्तर - अस्थायी का दूसरा, अस्थायी का दूसरा सेट करें:=0
• वापसी का तापमान
• मुख्य विधि से, यह नोड्स, माता-पिता सरणी और मान सरणी लेगा
• n :=मान सरणी में मौजूद मानों की संख्या
• उत्तर:=n
• आकार n + 1 के सरणी ग्राफ़ को परिभाषित करें
• मैं के लिए 1 से n - 1 की सीमा में
  • मैं ग्राफ़ में सम्मिलित करता हूं[parent[i]]
• dfs(0, मान, ग्राफ़)
• वापसी उत्तर

उदाहरण(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