सी++ में पथ योग III

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

अगर पेड़ [5,4,8,11,null,13,4,7,2,null,null,5,1] जैसा है, और योग 22 है, तो यह होगा -

पथ हैं [[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;
   }
};
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, ],]