मान लीजिए हमारे पास एक ट्री का रूट है। हमें सबसे अधिक बार आने वाला सबट्री योग (subtree sum) ढूंढना है। एक नोड का सबट्री योग उस नोड को रूट मानने वाले सबट्री के सभी नोड मानों का योग है (नोड स्वयं सहित)। यदि टाई हो, तो उच्चतम आवृत्ति वाले सभी मान किसी भी क्रम में लौटाएँ।
उदाहरण: ट्री [5,2,-5] के लिए आउटपुट [2] होगा (2 दो बार आता है, -5 एक बार)।
पोस्ट-ऑर्डर + फ्रीक्वेंसी मैप
- दो मैप्स:
freq(योग → आवृत्ति) औरsums(आवृत्ति → योगों की सूची)। - रिकर्सिव
solve(node):- यदि
nodenull है, तो 0 लौटाएँ। leftSum = solve(node->left),rightSum = solve(node->right)।currSum = node->val + leftSum + rightSum।freq[currSum]++।sums[freq[currSum]].push_back(currSum)।currSumलौटाएँ।
- यदि
- मुख्य फंक्शन:
solve(root)कॉल करें, फिरsumsकी सबसे बड़ी कुंजी (उच्चतम आवृत्ति) की सूची लौटाएँ।
C++ कार्यान्वयन
#include <bits/stdc++.h>
using namespace std;
class TreeNode {
public:
int val;
TreeNode *left, *right;
TreeNode(int data) { val = data; left = NULL; right = NULL; }
};
class Solution {
public:
map<int, int> freq;
map<int, vector<int>> sums;
int solve(TreeNode* node) {
if (!node) return 0;
int leftSum = solve(node->left);
int rightSum = solve(node->right);
int currSum = node->val + leftSum + rightSum;
freq[currSum]++;
sums[freq[currSum]].push_back(currSum);
return currSum;
}
vector<int> findFrequentTreeSum(TreeNode* root) {
freq.clear(); sums.clear();
if (!root) return {};
solve(root);
return sums.rbegin()->second; // सबसे बड़ी आवृत्ति की सूची
}
};
int main() {
// ट्री बनाने का कोड
Solution ob;
// auto res = ob.findFrequentTreeSum(root);
return 0;
}
इनपुट
[5,2,-5]
आउटपुट
[2, ]