ধরুন আমাদের একটি বাইনারি সার্চ ট্রি (BST) এর প্রি-অর্ডার ট্রাভার্সাল আছে। আমাদের প্রতিটি অভ্যন্তরীণ নোডে শুধুমাত্র একটি শিশু আছে কিনা তা পরীক্ষা করতে হবে৷
সুতরাং, যদি ইনপুটটি প্রি-অর্ডারের মত হয় =[22, 12, 13, 15, 14], তাহলে আউটপুটটি True হবে কারণ BST এর মত −
এটি সমাধান করার জন্য, আমরা একটি কার্যকর পদ্ধতি অনুসরণ করতে পারি। যেহেতু একটি নোডের সমস্ত ডিসেডেন্ট হয় ছোট বা বড়, তাহলে আমরা এই ধাপগুলি অনুসরণ করতে পারি -
-
নোডের পরবর্তী প্রি-অর্ডার উত্তরাধিকারী পান
-
নোডের শেষ প্রি-অর্ডার উত্তরাধিকারী পান
-
এখন যখন উভয় উত্তরসূরী বর্তমান নোডের চেয়ে কম বা বেশি হয় তখন আবার চেক করুন অন্যথায় মিথ্যা ফেরত দিন।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- পরবর্তী :=0, শেষ :=0
- আমি রেঞ্জ 0 থেকে প্রি-অর্ডারের আকার - 1 এর জন্য, করুন
- পরবর্তী :=প্রি-অর্ডার[i] - প্রি-অর্ডার[i+1]
- শেষ :=প্রি-অর্ডার[i] - প্রি-অর্ডারের শেষ মান
- যদি পরবর্তী * শেষ <0 হয়, তাহলে
- মিথ্যে ফেরত দিন
- সত্য ফেরান
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
উদাহরণ
def solve(preorder): next = 0 last = 0 for i in range(len(preorder)-1): next = preorder[i] - preorder[i+1] last = preorder[i] - preorder[-1] if next * last < 0: return False return True preorder = [22, 12, 13, 15, 14] print(solve(preorder))
ইনপুট
[22, 12, 13, 15, 14]
আউটপুট
True
