ধরুন আমাদের একটি বাইনারি সার্চ ট্রি এবং একটি টার্গেট মান আছে; আমাদের পরীক্ষা করতে হবে BST-তে দুটি উপাদান আছে কি না যাতে তাদের যোগফল প্রদত্ত লক্ষ্যের সমান বা না।
সুতরাং, যদি ইনপুট মত হয়
তাহলে আউটপুট হবে True।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
একটি অ্যারে v
সংজ্ঞায়িত করুন -
একটি ফাংশন ইনঅর্ডার(), এটি রুট করবে,
-
যদি মূল শূন্য হয়, তাহলে −
-
ফেরত
-
-
ইনঅর্ডার (মূলের বামে)
-
v
-এ রুটের মান সন্নিবেশ করান -
ইনঅর্ডার (মূলের বামে)
-
একটি ফাংশন findnode(), এটি k,
লাগবে -
n :=v
এর আকার -
যখন আমি
করি -
t :=v[i] + v[j]
-
t যদি k এর মত হয়, তাহলে −
-
প্রত্যাবর্তন সত্য
-
-
যদি t
-
(i 1 দ্বারা বাড়ান)
-
-
অন্যথায়
-
(j 1 দ্বারা কমিয়ে দিন)
-
-
-
মিথ্যা ফেরত দিন
-
প্রধান পদ্ধতি থেকে নিম্নলিখিতগুলি করুন -
-
inorder(root)
-
অ্যারে সাজান v
-
ফাইন্ডনোড(কে)
ফেরত দিন
উদাহরণ
আরো ভালোভাবে বোঝার জন্য নিচের বাস্তবায়নটি দেখি -
#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: vector<int> v; void inorder(TreeNode* root){ if (root == NULL || root->val == 0) return; inorder(root->left); v.push_back(root->val); inorder(root->right); } bool findnode(int k){ int n = v.size(), i = 0, j = n - 1; while (i < j) { int t = v[i] + v[j]; if (t == k) return true; if (t < k) i++; else j--; } return false; } bool findTarget(TreeNode* root, int k){ inorder(root); sort(v.begin(), v.end()); return findnode(k); } }; main(){ Solution ob; vector<int> v = {5,3,6,2,4,NULL,7}; TreeNode *root = make_tree(v); cout << (ob.findTarget(root, 9)); }
ইনপুট
{5,3,6,2,4,NULL,7},9
আউটপুট
1