মনে করুন একটি BST এবং low, high দুটি মান আছে। [low, high] রেঞ্জের বাইরে থাকা সব নোড ডিলিট করতে হবে।
ইনপুট ট্রি, low=7, high=10 হলে আউটপুট ট্রি (৭,৮,৯,১০) থাকবে। ছবি দেওয়া আছে।
সমাধানের ধাপসমূহ
- solve() ফাংশন সংজ্ঞায়িত করুন যা root, low, high নেয়
- যদি root null হয়, ফেরত যান
- যদি low > root.data, solve(root.right, low, high) ফেরত দিন
- যদি high < root.data, solve(root.left, low, high) ফেরত দিন
- root.right = solve(root.right, low, high)
- root.left = solve(root.left, low, high)
- root ফেরত দিন
উদাহরণ
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,
