C++ में टू सम BSTs

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

और टार्गेट 5 है, तो परिणाम true होगा।

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

• s नामक एक मैप परिभाषित करें
• check() नामक एक मेथड परिभाषित करें, जो नोड, टार्गेट और nodeNumber लेगा, यह निम्नानुसार काम करेगा -
• यदि नोड वैध है, तो false लौटाएं
• curr := नोड का मान, req := टार्गेट - curr
• यदि req s में मौजूद है और s[req] nodeNumber नहीं है, तो true लौटाएं
• s[curr] := nodeNumber
• check(नोड का लेफ्ट, टार्गेट, nodeNumber) OR check(नोड का राइट, टार्गेट, nodeNumber) लौटाएं
• मेन मेथड में, हम सेट करेंगे -
• flag := check(root1, टार्गेट, 1)
• check(root2, टार्गेट, 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