ধরুন আমাদের একটি বাইনারি সার্চ ট্রি এবং এতে একটি নোড আছে, আমাদের BST-এ সেই নোডের ইন-অর্ডার উত্তরাধিকারী অনুসন্ধান করতে হবে। আমরা জানি যে একটি নোড p-এর উত্তরসূরি হল p.val-এর চেয়ে ছোট কী সহ নোড।
সুতরাং, যদি ইনপুট রুট =[2,1,3], p =1,
এর মত হয়
তাহলে আউটপুট হবে 2,
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
পুনরাবৃত্ত পদ্ধতি সংজ্ঞায়িত করুন inorderSuccessor(), এটি রুট এবং p
নেবে -
যদি রুট নাল হয়, তাহলে −
-
রিটার্ন নাল
-
-
যদি মূলের val <=p এর val, তাহলে −
-
রিটার্ন inorderSuccessor(রুটের ডান , p)
-
-
অন্যথায়
-
বিকল্প :=inorderSuccessor(রুটের বামে , p)
-
রিটার্ন (যদি বিকল্প শূন্য হয়, তাহলে রুট, অন্যথায় বিকল্প)
-
উদাহরণ
আরো ভালোভাবে বোঝার জন্য নিচের বাস্তবায়নটি দেখি -
#include <bits/stdc++.h> using namespace std; class TreeNode{ public: int val; TreeNode *left, *right; TreeNode(int data){ val = data; left = NULL; right = NULL; } }; class Solution { public: TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) { if(!root) return NULL; if(root->val <= p->val){ return inorderSuccessor(root->right, p); } else{ TreeNode* option = inorderSuccessor(root->left, p); return !option ? root : option; } } }; main(){ TreeNode *root = new TreeNode(2); root->left = new TreeNode(1); root->right = new TreeNode(3); TreeNode *p = root->left; Solution ob; cout << (ob.inorderSuccessor(root, p))->val; }
ইনপুট
{2,1,3},1
আউটপুট
2