ধরুন আমাদের একটি গাছের মূল আছে, আমাদের সবচেয়ে ঘন ঘন সাবট্রি যোগফল খুঁজে বের করতে হবে। একটি নোডের সাবট্রি সমষ্টি আসলে সেই নোডের মূল উপবৃক্ষ দ্বারা গঠিত সমস্ত নোড মানগুলির সমষ্টি (নোডটি নিজেই সহ)। সবচেয়ে ঘন ঘন সাবট্রি যোগফল হল আসলে যদি একটি টাই থাকে, যে কোনও ক্রমে সর্বোচ্চ ফ্রিকোয়েন্সি সহ সমস্ত মান ফেরত দিন। সুতরাং যদি গাছটি [5,2,-5] এর মতো হয় তবে এটি [2] ফিরে আসবে। এর কারণ হল 2 দুইবার হয়, তবে -5 শুধুমাত্র একবার ঘটে।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
m এবং freq দুটি মানচিত্র সংজ্ঞায়িত করুন, m হল পূর্ণসংখ্যা কী এবং একটি সংশ্লিষ্ট তালিকার একটি সেট, এবং freq প্রতিটি সংখ্যার ফ্রিকোয়েন্সি সংরক্ষণ করবে।
-
সমাধান() নামক একটি পদ্ধতি সংজ্ঞায়িত করুন, এটি ট্রি নোড নেবে। এটি নিম্নরূপ কাজ করবে -
-
যদি নোড শূন্য হয়, তাহলে 0
ফেরত দিন -
leftSum :=সমাধান(নোডের বামে), rightSum :=solve(নোডের ডানদিকে)
-
currSum :=নোড মান + leftSum + rightSum
-
যদি ফ্রিকোয়েন্সি গণনা currSum এর সমান না হয়, তাহলে
-
m[1]
-এ উপস্থিত তালিকায় currSum সন্নিবেশ করান -
সেট ফ্রিকোয়েন্সি [currSum] :=1
-
-
অন্যথায়
-
ফ্রিকোয়েন্সি [currSum] 1 দ্বারা বৃদ্ধি করুন
-
m[freq[currSum]]
-এ উপস্থিত তালিকায় currSum সন্নিবেশ করান
-
-
currSum ফেরত দিন
-
মূল পদ্ধতিটি হবে −
এর মত -
যদি রুট শূন্য হয়, তাহলে খালি সেট ফেরত দিন
-
সমাধান(রুট)
-
m
মানচিত্রের শেষ তালিকা ফেরত দিন
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
class TreeNode{
public:
int val;
TreeNode *left, *right;
TreeNode(int data){
val = data;
left = NULL;
right = NULL;
}
};
void insert(TreeNode **root, int val){
queue<TreeNode*> q;
q.push(*root);
while(q.size()){
TreeNode *temp = q.front();
q.pop();
if(!temp->left){
if(val != NULL)
temp->left = new TreeNode(val);
else
temp->left = new TreeNode(0);
return;
}else{
q.push(temp->left);
}
if(!temp->right){
if(val != NULL)
temp->right = new TreeNode(val);
else
temp->right = new TreeNode(0);
return;
} else {
q.push(temp->right);
}
}
}
TreeNode *make_tree(vector<int> v){
TreeNode *root = new TreeNode(v[0]);
for(int i = 1; i<v.size(); i++){
insert(&root, v[i]);
}
return root;
}
class Solution {
public:
map <int, vector <int> > m;
map <int, int > freq;
int solve(TreeNode* node){
if(!node)return 0;
int leftSum = solve(node->left);
int rightSum = solve(node->right);
int currSum = node->val + leftSum + rightSum;
//cout << currSum << endl;
if(!freq.count(currSum)){
m[1].push_back(currSum);
freq[currSum] = 1;
//cout << "Adding " << currSum << " 1" << endl;
} else {
freq[currSum]++;
m[freq[currSum]].push_back(currSum);
}
return currSum;
}
vector<int> findFrequentTreeSum(TreeNode* root) {
m.clear();
freq.clear();
if(!root)return {};
solve(root);
return m.rbegin()->second;
}
};
main(){
vector<int> v = {5,2,-5};
TreeNode *tree = make_tree(v);
Solution ob;
print_vector(ob.findFrequentTreeSum(tree));
} ইনপুট
[5,2,-5]
আউটপুট
[2, ]
