পাইথনে বিএসটি-তে প্রদত্ত যোগফল সহ একটি ট্রিপলেট বিদ্যমান কিনা তা পরীক্ষা করুন

ধরুন, আমাদের একটি বাইনারি সার্চ ট্রি (BST) দেওয়া হয়েছে যাতে পূর্ণসংখ্যার মান এবং একটি সংখ্যা 'মোট' রয়েছে। প্রদত্ত BST-তে তিনটি উপাদানের কোনো গ্রুপ আছে কিনা তা আমাদের খুঁজে বের করতে হবে যেখানে তিনটি উপাদান যোগ করা 'মোট' মানের সমান।

সুতরাং, যদি ইনপুট মত হয়

মোট =12, তাহলে আউটপুট হবে True।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• temp_list :=শূন্য দিয়ে শুরু করা একটি নতুন তালিকা
• গাছটি ট্রাভার্স করে টেম্প_লিস্টে রাখুন
• আমি 0 থেকে পরিসরে (temp_list - 2 এর আকার), 1 দ্বারা বাড়ান, করুন
  • বামে :=i + 1
  • ডান:=temp_list - 1 এর আকার
  • যখন বাম <ডানে, কর
    • যদি temp_list[i] + temp_list[left] + temp_list[right] যোগফলের সমান হয়, তাহলে
      • সত্য ফেরান
    • অন্যথায় যখন temp_list[i] + temp_list[left] + temp_list[right] <যোগফল অ-শূন্য, তারপর
      • বাম :=বাম + 1
    • অন্যথায়,
      • ডান:=ডান - 1
• মিথ্যে ফেরত দিন

উদাহরণ

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

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