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

C++ में पाथ सम III - रूट से लीफ तक दिए गए योग वाले पाथ ढूंढना


मान लीजिए हमारे पास एक बाइनरी ट्री है जिसमें प्रत्येक नोड एक पूर्णांक मान रखता है। हमें उन पाथ को ढूंढना है जिनका योग दिए गए मान के बराबर हो। पाथ रूट से लीफ तक होना चाहिए।

समस्या विवरण

यदि ट्री है [5,4,8,11,null,13,4,7,2,null,null,5,1] और योग 22 है, तो परिणाम होगा -

C++ में पाथ सम III - रूट से लीफ तक दिए गए योग वाले पाथ ढूंढना

पाथ हैं: [[5,4,11,2],[5,8,4,5]]

एल्गोरिदम

इसे हल करने के लिए हम DFS (डेप्थ-फर्स्ट सर्च) का उपयोग करेंगे जो थोड़ा संशोधित है:

  • DFS फंक्शन रूट, शेष योग, और एक अस्थायी ऐरे लेता है
  • यदि रूट मौजूद नहीं है, तो लौट जाएं
  • यदि रूट का बायां और दायां दोनों खाली हैं (लीफ नोड), तो:
    • यदि शेष योग रूट के मान के बराबर है, तो रूट के मान को अस्थायी ऐरे में जोड़ें, अस्थायी ऐरे को परिणाम में जोड़ें, और अंतिम नोड को अस्थायी ऐरे से हटाएं
  • रूट के मान को अस्थायी ऐरे में डालें
  • बाएं सबट्री के लिए DFS कॉल करें (शेष योग - रूट का मान)
  • दाएं सबट्री के लिए DFS कॉल करें (शेष योग - रूट का मान)
  • अस्थायी ऐरे से अंतिम तत्व हटाएं (बैकट्रैकिंग)

उदाहरण

#include <bits/stdc++.h> 
using namespace std; 

void print_vector(vector<vector<int> > v) { 
    cout << "["; 
    for(int i = 0; i < v.size(); i++) { 
        cout << "["; 
        for(int j = 0; j < v[i].size(); j++) { 
            cout << v[i][j] << ", "; 
        } 
        cout << "],"; 
    } 
    cout << "]" << endl; 
} 

class TreeNode { 
public: 
    int val; 
    TreeNode *left, *right; 
    TreeNode(int data) { 
        val = data; 
        left = 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: 
    vector<vector<int>> res; 
    void dfs(TreeNode* root, int sum, vector<int>& temp) { 
        if(!root) return; 
        if(!root->left && !root->right) { 
            if(sum == root->val) { 
                temp.push_back(root->val); 
                res.push_back(temp); 
                temp.pop_back(); 
            } 
            return; 
        } 
        temp.push_back(root->val); 
        dfs(root->left, sum - root->val, temp); 
        dfs(root->right, sum - root->val, temp); 
        temp.pop_back(); 
    } 
    vector<vector<int>> pathSum(TreeNode* root, int sum) { 
        res.clear(); 
        vector<int> temp; 
        dfs(root, sum, temp); 
        return res; 
    } 
}; 

int main() { 
    Solution ob; 
    vector<int> v = {5,4,8,11,NULL,13,4,7,2,NULL,NULL,NULL,NULL,5,1}; 
    TreeNode *root = make_tree(v); 
    print_vector(ob.pathSum(root, 22)); 
}

इनपुट

[5,4,8,11,null,13,4,7,2,null,null,5,1] 22

आउटपुट

[[5, 4, 11, 2, ],[5, 8, 4, 5, ],]

  1. C++ में जांचें कि क्या रूट से लीफ पथ में कोई जोड़ा है जिसका योग रूट के डेटा के बराबर है C++ में जांचें कि क्या रूट से लीफ पथ में कोई जोड़ा है जिसका योग रूट के डेटा के बराबर है

    इस समस्या में, हमें एक बाइनरी ट्री दिया गया है। और हमें जांचना है कि क्या रूट से लीफ पथ में कोई जोड़ा है जिसका योग रूट के डेटा के बराबर है। हमें जांचना है कि क्या नोड्स का कोई जोड़ा मौजूद है जो रूट नोड से लीफ नोड्स के बीच स्थित है जैसे कि जोड़े के मानों का योग रूट नोड के मान के बराबर है। समस्या को

  1. C++ में बाइनरी ट्री में अधिकतम पथ योग C++ में बाइनरी ट्री में अधिकतम पथ योग

    इस समस्या में, हमें एक बाइनरी ट्री दिया गया है जिसमें प्रत्येक नोड एक मान रखता है। हमारा कार्य बाइनरी ट्री के दो पत्तों के बीच अधिकतम पथ योग ढूंढने के लिए एक प्रोग्राम बनाना है। यहां, हमें एक पत्ते नोड से दूसरे पत्ते नोड तक का पथ ढूंढना है जो मानों का अधिकतम योग प्रदान करेगा। यह अधिकतम योग पथ रूट न

  1. पायथन में पथ योग पायथन में पथ योग

    मान लीजिए हमारे पास एक ट्री और एक योग है। हमें एक ऐसा पथ ढूंढना है जिससे यदि हम उस पथ का अनुसरण करें, तो हमें वह योग मिलेगा जो दिए गए योग से मेल खाता हो। मान लीजिए ट्री [0,-3,9,-10, null,5] जैसा है और योग 14 है, तो एक पथ 0 → 9 → 5 है। हल करने के चरण यदि रूट null है, तो False वापस करें यदि बायां औ