মান লেি, আমাদের কাছে একটি বাইনারি সার্চ ট্রি (BST) আছে যাতে পূর্ণসংখ্যা মান থাকে, এবং একটি 숫ার 'total'। আমাদের খুঁজে বের করতে হবে BST-তে তিনটি উপাদানের কোনো গুচ্ছ আছে কিনা যাদের যোগফল প্রদত্ত 'total' মানের সমান।
যেমন, ইনপুট হলে (ট্রি চিত্র অনুযায়ী) total = 12, তবে আউটপুট হবে True।
এটি সমাধান করতে আমরা নিচের ধাপগুলো অনুসরণ করব:
- temp_list := শূন্য দিয়ে আরম্ভ করা একটি নতুন লিস্ট।
- ট্রি-কে ইনঅর্ডার ট্রাভার্স করুন এবং temp_list-এ রাখুন।
- i কে 0 থেকে (temp_list-এর সাইজ - 2) পর্যন্ত ১ করে বাড়িয়ে লুপ চালান:
- left := i + 1
- right := temp_list-এর সাইজ - 1
- যখন left < right, তখন লুপ চালান:
- যদি temp_list[i] + temp_list[left] + temp_list[right] sum-এর সমান হয়, তবে True রিটার্ন করুন।
- অন্যথায় যখন temp_list[i] + temp_list[left] + temp_list[right] < sum হয়, তবে left := left + 1।
- অন্যথায়, right := right - 1।
- False রিটার্ন করুন।
উদাহরণ
বेहतर বোঝার জন্য নিচের ইমপ্লিমেন্টেশনটি দেখুন:
class TreeNode:
def __init__(self, value):
self.value = value
self.right = None
self.left = None
def traverse_inorder(tree_root, inorder):
if tree_root is None:
return
traverse_inorder(tree_root.left, inorder)
inorder.append(tree_root.value)
traverse_inorder(tree_root.right, inorder)
def solve(tree_root, sum):
temp_list = [0]
traverse_inorder(tree_root, temp_list)
for i in range(0, len(temp_list) - 2, 1):
left = i + 1
right = len(temp_list) - 1
while(left < right):
if temp_list[i] + temp_list[left] + temp_list[right] == sum:
return True
elif temp_list[i] + temp_list[left] + temp_list[right] < sum:
left += 1
else:
right -= 1
return False
tree_root = TreeNode(5)
tree_root.left = TreeNode(3)
tree_root.right = TreeNode(7)
tree_root.left.left = TreeNode(2)
tree_root.left.right = TreeNode(4)
tree_root.right.left = TreeNode(6)
tree_root.right.right = TreeNode(8)
print(solve(tree_root, 12))
ইনপুট
tree_root = TreeNode(5) tree_root.left = TreeNode(3) tree_root.right = TreeNode(7) tree_root.left.left = TreeNode(2) tree_root.left.right = TreeNode(4) tree_root.right.left = TreeNode(6) tree_root.right.right = TreeNode(8) 12
আউটপুট
True
