মনে করুন একটি ট্রি আছে, এই ট্রি নোড 0-তে রুটেড, এটি নিচের মোতাবিক দেওয়া হয় -
- নোডের সংখ্যা `nodes`
- `i`-তম নোডের মান `value[i]`
- `i`-তম নোডের পেরেন্ট `parent[i]`
আমাদের যেসব সাবট্রির নোডগুলোর মানগুলোর যোগফল ০, সেগুলো মুছে ফেলতে হবে, তারপর ট্রিতে অবশিষ্ট নোডের সংখ্যা রিটার্ন করতে হবে। যদি ট্রি নিচের মোতাবিক হয় -
৭টি নোড আছে, আউটপুট হবে ২।
এটি সমাধান করতে আমরা নিচের ধাপগুলো অনুসরণ করব -
- `children` নামক একটি ম্যাপ তৈরি করুন
- `dfs()` নামক একটি মেথড সংজ্ঞায়িত করুন, এটি `node`, `value` অ্যারে এবং `graph` নেবে
- `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`, `parents` অ্যারে এবং `values` অ্যারে নেবে
- `n` := `values` অ্যারেতে উপস্থিত ভ্যালুর সংখ্যা
- `ans := n`
- `graph` নামক একটি অ্যারে আকার `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
