सी++ में दो योग बीएसटी

मान लीजिए कि हमारे पास दो बाइनरी सर्च ट्री हैं, हमें ट्रू वापस करना होगा यदि पहले ट्री में एक नोड और दूसरे ट्री में एक नोड है और इन नोड्स का योग एक पूर्णांक लक्ष्य है . तो अगर पेड़ जैसा है -

और लक्ष्य 5 है, तो परिणाम सत्य है।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• मानचित्र को परिभाषित करें
• चेक () नामक एक विधि को परिभाषित करें, यह नोड, लक्ष्य और नोडनंबर लेगा, यह निम्नानुसार काम करेगा -
• यदि नोड मान्य है, तो झूठी वापसी करें
• curr :=नोड का मान, req :=target – curr
• यदि s में req मौजूद है और s[req] nodeNumber नहीं है, तो true वापस करें
• s[curr] :=nodeNumber
• रिटर्न चेक (नोड, टारगेट, नोड नंबर के बाएं) या चेक (नोड, टारगेट, नोडनंबर के दाएं)
• मुख्य विधि में, हम सेट करेंगे -
• झंडा :=चेक (रूट1, लक्ष्य, 1)
• रिटर्न चेक(रूट2, लक्ष्य, 2)

उदाहरण(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;
      }
};
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,int> s;
   bool check(TreeNode* node, int target,int nodeNumber){
      if(!node)return false;
      int curr = node->val;
      int req = target - curr;
      if(s.find(req)!=s.end() && s[req]!=nodeNumber)return true;
      s[curr]=nodeNumber;
      return check(node->left,target,nodeNumber) || check(node->right,target,nodeNumber);
   }
   bool twoSumBSTs(TreeNode* root1, TreeNode* root2, int target) {
      bool flag = check(root1,target,1);
      return check(root2,target,2);
   }
};
main(){
   vector<int> v1 = {2,1,4};
   vector<int> v2 = {1,0,3};
   TreeNode *r1 = make_tree(v1);
   TreeNode *r2 = make_tree(v2);
   Solution ob;
   cout <<ob.twoSumBSTs(r1, r2, 5);
}

इनपुट

[2,1,4]
[1,0,3]
5

आउटपुट

1