ধরুন আমাদের একটি BST আছে, একটি দুটি মান নিম্ন এবং উচ্চ, আমাদের সমস্ত নোড মুছে ফেলতে হবে যেগুলি [নিম্ন, উচ্চ] (অন্তর্ভুক্ত) এর মধ্যে নয়।
সুতরাং, যদি ইনপুট মত হয়
low =7 high =10, তাহলে আউটপুট হবে
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- একটি ফাংশন সংজ্ঞায়িত করুন solve()। এটি রুট, নিম্ন, উচ্চ গ্রহণ করবে
- যদি রুট নাল হয়, তাহলে
- প্রত্যাবর্তন
- যদি কম> রুটের ডেটা, তাহলে
- রিটার্ন সলভ (মূলের ডান, নিম্ন, উচ্চ)
- উচ্চ হলে <রুটের ডেটা, তারপর
- রিটার্ন সলভ (মূলের বামে, নিম্ন, উচ্চ)
- মূলের অধিকার :=সমাধান (মূলের ডান, নিম্ন, উচ্চ)
- মূলের বামে :=সমাধান (মূলের বামে, নিম্ন, উচ্চ)
- রিটার্ন রুট
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
উদাহরণ
class TreeNode: def __init__(self, data, left = None, right = None): self.data = data self.left = left self.right = right def print_tree(root): if root is not None: print_tree(root.left) print(root.data, end = ', ') print_tree(root.right) class Solution: def solve(self, root, low, high): if not root: return if low > root.data: return self.solve(root.right,low,high) if high < root.data: return self.solve(root.left,low,high) root.right = self.solve(root.right,low,high) root.left = self.solve(root.left,low,high) return root 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) low = 7 high = 10 ret = ob.solve(root, low, high) print_tree(ret)
ইনপুট
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) low = 7 high = 10
আউটপুট
7, 8, 9, 10,