ধরুন আমাদের বাইনারি গাছ আছে; এটি একটি বাইনারি অনুসন্ধান গাছ কিনা তা আমাদের পরীক্ষা করতে হবে। আমরা জানি একটি BST এর নিম্নলিখিত বৈশিষ্ট্য রয়েছে -
- এর বাম সাবট্রির সমস্ত নোড বর্তমান নোড মানের থেকে ছোট
- এর ডান সাবট্রির সমস্ত নোড বর্তমান নোডের মান থেকে বড়
- সব নোডের জন্য এই বৈশিষ্ট্যগুলি পুনরাবৃত্তিমূলকভাবে ধরে রাখে
সুতরাং, যদি ইনপুট মত হয়
তাহলে আউটপুট হবে True
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- x :=গাছের উপাদানের ক্রমবর্ধমান ট্রাভার্সাল সিকোয়েন্সের একটি তালিকা
- যদি x সাজানো হয়, তাহলে
- সত্য ফেরত দিন
- মিথ্যে ফেরত দিন
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
উদাহরণ
class TreeNode: def __init__(self, data, left = None, right = None): self.data = data self.left = left self.right = right class Solution: def solve(self, root): def inorder(root,l): if root is None: return inorder(root.left,l) l.append(root.data) inorder(root.right,l) l = [] inorder(root,l) return l == sorted(l) ob = Solution() root = TreeNode(5) root.left = TreeNode(1) root.right = TreeNode(9) root.right.left = TreeNode(7) root.right.right = TreeNode(10) root.right.left.left = TreeNode(6) root.right.left.right = TreeNode(8) print(ob.solve(root))
ইনপুট
root = TreeNode(5) root.left = TreeNode(1) root.right = TreeNode(9) root.right.left = TreeNode(7) root.right.right = TreeNode(10) root.right.left.left = TreeNode(6) root.right.left.right = TreeNode(8)
আউটপুট
True
