পাইথনের একটি বাইনারি গাছে দুটি উপাদানের মধ্যে সাধারণ একটি পূর্বপুরুষ খুঁজে বের করার প্রোগ্রাম

ধরুন আমাদের একটি বাইনারি ট্রি আছে, এবং আমাদের দুটি সংখ্যা a এবং b আছে, আমাদেরকে সর্বনিম্ন নোডের মান খুঁজে বের করতে হবে যার বংশধর হিসাবে a এবং b আছে। আমাদের মনে রাখতে হবে যে একটি নোড নিজেই একটি বংশধর হতে পারে।

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

a =6, b =2, তাহলে আউটপুট হবে 4

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

• একটি পদ্ধতি সংজ্ঞায়িত করুন solve() এটি রুট এবং a, b

  নেবে

• যদি রুট শূন্য হয়, তাহলে

  • রিটার্ন -1

• যদি রুটের মান হয় a বা b, তাহলে

  • রুটের রিটার্ন মান

• left :=সমাধান (মূলের বাম, a, b)

• ডান :=সমাধান (মূলের ডান, a, b)

• যদি বাম বা ডান -1 না হয়, তাহলে

  • রুটের রিটার্ন মান

• বাম দিকে ফিরুন যদি বাম -1 এর মত না হয় অন্যথায় ডান

• মূল পদ্ধতি কল সল্ভ(রুট)

  থেকে

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

উদাহরণ

class TreeNode:
   def __init__(self, val, left=None, right=None):
      self.val = val
      self.left = left
      self.right = right

class Solution:
   def solve(self, root, a, b):
      if not root:
         return -1
      if root.val in (a, b):
         return root.val
      left = self.solve(root.left, a, b)
      right = self.solve(root.right, a, b)
      if -1 not in (left, right):
         return root.val
      return left if left != -1 else right
ob = Solution()
root = TreeNode(3)
root.left = TreeNode(10)
root.right = TreeNode(4)
root.right.left = TreeNode(8)
root.right.right = TreeNode(2)
root.right.left.left = TreeNode(6)
print(ob.solve(root, 6, 2))

ইনপুট

root = TreeNode(3)
root.left = TreeNode(10)
root.right = TreeNode(4)
root.right.left = TreeNode(8)
root.right.right = TreeNode(2)
root.right.left.left = TreeNode(6)
6, 2

আউটপুট

4