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

ধরুন, আমাদের একটি বাইনারি ট্রি দেওয়া হয়েছে এবং এছাড়াও দুটি নির্দিষ্ট নোড x এবং y দেওয়া হয়েছে। আমাদের বাইনারি গাছ থেকে দুটি নোডের সর্বনিম্ন সাধারণ পূর্বপুরুষ খুঁজে বের করতে হবে। একটি বাইনারি গাছের সর্বনিম্ন সাধারণ পূর্বপুরুষ হল সর্বনিম্ন নোড যার মধ্যে x এবং y উভয় নোডই এর বংশধর। এছাড়াও, একটি নির্দিষ্ট নোড নিজেই একটি বংশধর হতে পারে। আমাদের নোডটি খুঁজে বের করতে হবে এবং এটিকে আউটপুট হিসাবে ফেরত দিতে হবে।

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

এবং x =2, y =4; তাহলে আউটপুট হবে 3.

যে নোডের নোড 2 এবং 4 3 এর বংশধর। তাই, 3 ফেরত দেওয়া হবে।

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

একটি ফাংশন dfs() সংজ্ঞায়িত করুন। এটি নোড গ্রহণ করবে
- যদি নোড নাল এর মত হয়, তাহলে
  - ফেরত
- যদি তালিকা [x,y]-এ নোড উপস্থিত থাকে, তাহলে
  - left :=dfs(নোডের বাম দিকে)
  - ডান:=dfs(নোডের ডানদিকে)
  - যদি বাম বা ডান অ-শূন্য হয়, তাহলে
    - উত্তর :=নোড
    - রিটার্ন নোড
- left :=dfs(নোডের বাম দিকে)
- ডান:=dfs(নোডের ডানদিকে)
- যদি বাম এবং ডান শূন্য না হয়, তাহলে
  - উত্তর :=নোড
  - রিটার্ন নোড
- বাম বা ডানে ফিরুন
উত্তর :=dfs(root)
উত্তর ফেরত দিন

উদাহরণ

class TreeNode:
def __init__(self, data, left = None, right = None):
   self.data = data
   self.left = left
   self.right = right
def insert(temp,data):
   que = []
   que.append(temp)
   while (len(que)):
      temp = que[0]
      que.pop(0)
      if (not temp.left):
      if data is not None:
         temp.left = TreeNode(data)
      else:
         temp.left = TreeNode(0)
         break
      else:
         que.append(temp.left)
      if (not temp.right):
      if data is not None:
         temp.right = TreeNode(data)
      else:
         temp.right = TreeNode(0)
         break
      else:
         que.append(temp.right)
def make_tree(elements):
   Tree = TreeNode(elements[0])
   for element in elements[1:]:
      insert(Tree, element)
      return Tree
def search_node(root, element):
   if (root == None):
      return None
   if (root.data == element):
      return root
      res1 = search_node(root.left, element)
   if res1:
      return res1
      res2 = search_node(root.right, element)
      return res2
def solve(root, x, y):
def dfs(node):
   if not node:
      return
   if node in [x,y]:
      left = dfs(node.left)
      right = dfs(node.right)
   if left or right:
      ans = node
      return node
      left = dfs(node.left)
      right = dfs(node.right)
   if left and right:
      ans = node
      return node
      return left or right
      ans = dfs(root)
   return ans
root = make_tree([5, 3, 7, 2, 4, 1, 7, 6, 8, 10])
print(solve(root, search_node(root, 2), search_node(root, 4)).data)

ইনপুট

make_tree([5, 3, 7, 2, 4, 1, 7, 6, 8, 10]),
search_node(root, 2),
search_node(root, 4)