Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ में सबसे अधिक बार आने वाला सबट्री योग


मान लीजिए हमारे पास एक ट्री का रूट है। हमें सबसे अधिक बार आने वाला सबट्री योग (subtree sum) ढूंढना है। एक नोड का सबट्री योग उस नोड को रूट मानने वाले सबट्री के सभी नोड मानों का योग है (नोड स्वयं सहित)। यदि टाई हो, तो उच्चतम आवृत्ति वाले सभी मान किसी भी क्रम में लौटाएँ।

उदाहरण: ट्री [5,2,-5] के लिए आउटपुट [2] होगा (2 दो बार आता है, -5 एक बार)।

पोस्ट-ऑर्डर + फ्रीक्वेंसी मैप

  1. दो मैप्स: freq (योग → आवृत्ति) और sums (आवृत्ति → योगों की सूची)।
  2. रिकर्सिव solve(node):
    • यदि node null है, तो 0 लौटाएँ।
    • leftSum = solve(node->left), rightSum = solve(node->right)।
    • currSum = node->val + leftSum + rightSum।
    • freq[currSum]++।
    • sums[freq[currSum]].push_back(currSum)।
    • currSum लौटाएँ।
  3. मुख्य फंक्शन: 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, ]
  1. C++ में ट्री में सबसे बड़ा उपट्री योग ढूंढें C++ में ट्री में सबसे बड़ा उपट्री योग ढूंढें

    इस समस्या में, हमें एक बाइनरी ट्री दिया गया है। हमारा कार्य ट्री में सबसे बड़ा उपट्री योग ढूंढना है। समस्या विवरण: बाइनरी ट्री में धनात्मक और ऋणात्मक दोनों मान होते हैं। और हमें वह उपट्री ढूंढनी है जिसमें नोड्स का अधिकतम योग हो। समस्या को समझने के लिए एक उदाहरण लेते हैं, आउटपुट: 13 व्याख्या: बाएं

  1. - C++ में पथ योग IV

    मान लीजिए हमारे पास पूर्णांकों की एक सूची है जो गहराई 5 से कम वाले बाइनरी ट्री को दर्शाती है। यदि ट्री की गहराई 5 से कम है, तो इस ट्री को तीन अंकों वाले पूर्णांकों की सूची द्वारा दर्शाया जा सकता है। इस सूची में प्रत्येक पूर्णांक के लिए: सैकड़ों अंक इस नोड की गहराई D को दर्शाता है, 1 <= D <= 4। दहा

  1. C++ में उल्टे उपट्री (Inverted Subtree) की जांच C++ में उल्टे उपट्री (Inverted Subtree) की जांच

    दो बाइनरी ट्री source और target दिए गए हैं। जांचें कि क्या source का कोई उल्टा रूप (inversion) target का उपट्री है। उल्टा रूप का अर्थ: बाएं और दाएं बच्चे वैकल्पिक रूप से स्वैप हो सकते हैं। रिकर्सिव जांच: दो ट्री उल्टे हैं यदि (बाएं-बाएं और दाएं-दाएं मेल खाते हैं) या (बाएं-दाएं और दाएं-बाएं मेल खाते