โปรแกรมหาบรรพบุรุษร่วมที่ต่ำที่สุดของไบนารีทรีโดยใช้ Python

สมมติว่าเราได้รับไบนารีทรีและโหนดเฉพาะสองโหนด x และ y เราต้องหาบรรพบุรุษร่วมที่ต่ำที่สุดของโหนดทั้งสองจากไบนารีทรี บรรพบุรุษร่วมที่ต่ำที่สุดในไบนารีทรีคือโหนดที่ต่ำที่สุดซึ่งทั้งโหนด x และ y เป็นลูกหลานของ นอกจากนี้ โหนดเฉพาะยังสามารถเป็นลูกหลานของตัวเองได้อีกด้วย เราต้องหาโหนดและส่งคืนเป็นเอาต์พุต

ดังนั้นหากอินพุตเป็นแบบ

และ x =2, y =4; แล้วผลลัพธ์จะเป็น 3

โหนดที่โหนด 2 และ 4 เป็นลูกหลานของคือ 3 ดังนั้น 3 จะถูกส่งคืน

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดฟังก์ชัน dfs() นี่จะใช้โหนด

  • ถ้าโหนดคล้ายกับ null แล้ว

    • กลับ

  • หากมีโหนดอยู่ในรายการ [x,y] ดังนั้น

    • ซ้าย :=dfs(ซ้ายของโหนด)

    • right :=dfs(ทางขวาของโหนด)

    • ถ้าทางซ้ายหรือทางขวาไม่เป็นศูนย์

      • ตอบ :=โหนด

      • โหนดกลับ

  • ซ้าย :=dfs(ซ้ายของโหนด)

  • right :=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)

ผลลัพธ์

3