ধরা যাক একটি ট্রির রুট দেওয়া আছে, আমরা সবচেয়ে বেশি ফ্রিকোয়েন্সি বিশিষ্ট সাবট্রি সমষ্টি (subtree sum) বের করব। একটি নোডের সাবট্রি সমষ্টি হলো সেই নোডকে রুট ধরে গঠিত সাবট্রির সব নোডের মান যোগফল (নোডটি নিজেও অন্তর্ভুক্ত)। সবচেয়ে বেশি ফ্রিকোয়েন্সি বিশিষ্ট সাবট্রি সমষ্টি হলো যদি টাই হয়, তবে সর্বোচ্চ ফ্রিকোয়েন্সি বিশিষ্ট সব মান যেকোনো ক্রমে রিটার্ন করতে হবে। যদি ট্রি হয় [5,2,-5], তবে এটি [2] রিটার্ন করবে। কারণ 2 দুবার হয়েছে, কিন্তু -5 শুধু একবার।
সমাধানের ধাপগুলো −
দুটি ম্যাপ m এবং freq সংজ্ঞা করব, m হলো ইন্টিজার কী এবং সংশ্লিষ্ট লিস্টের সেট, আর freq প্রতিটি সংখ্যার ফ্রিকোয়েন্সি স্টোর করবে।
solve() নামে একটি মেথড সংজ্ঞা করব, যা ট্রি নোড নিবে। এটি নিচেরভাবে কাজ করবে −
যদি নোড null হয়, তবে 0 রিটার্ন করব
leftSum := solve(নোডের বাম), rightSum := solve(নোডের ডান)
currSum := নোডের মান + leftSum + rightSum
যদি ফ্রিকোয়েন্সি কাউন্ট currSum-এর সাথে মিলে না, তবে
currSum m[1]-এ উপস্থিত লিস্টে ইনসার্ট করব
freq[currSum] := 1 সেট করব
অন্যথায়
freq[currSum] ১ বাড়াব
currSum m[freq[currSum]]-এ উপস্থিত লিস্টে ইনসার্ট করব
currSum রিটার্ন করব
মেইন মেথডটি নিচের মতো হবে −
যদি রুট null হয়, তবে খালি সেট রিটার্ন করব
solve(root)
ম্যাপ 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, ]
