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

สมมติว่าเราได้รับไบนารีทรีและขอให้ค้นหาบรรพบุรุษร่วมที่ต่ำที่สุดของโหนดทั้งหมดในทรี บรรพบุรุษร่วมที่ต่ำที่สุดในไบนารีทรีคือโหนดต่ำสุดที่โหนด x1, x2, x3,...., xn เป็นลูกหลาน โหนดใดโหนดหนึ่งสามารถเป็นลูกหลานของตัวเองได้เช่นกัน เราต้องหาโหนดและส่งคืนเป็นเอาต์พุต อินพุตคือโหนดรูทของต้นไม้และรายการโหนดที่เราต้องหาต้นทาง

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

และรายชื่อโหนดที่เราต้องหาบรรพบุรุษคือ [6, 8]; แล้วผลลัพธ์จะเป็น 7

ผลลัพธ์คือ 7 เนื่องจากโหนดต่ำสุดที่โหนด 6 และ 8 เป็นลูกหลานคือ 7

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

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

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

    • โหนดกลับ

  • มิฉะนั้น เมื่อโหนดถูกตั้งค่าล่วงหน้าในโหนด ดังนั้น

    • โหนดกลับ

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

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

  • ถ้าซ้ายและขวาไม่เป็นโมฆะ

    • โหนดกลับ

  • มิฉะนั้น

    • ถ้าซ้ายหรือขวาไม่เป็นโมฆะ

      • โหนดกลับ

• nodes :=รายการใหม่

• สำหรับแต่ละองค์ประกอบใน node_list ให้ทำ

  • แทรก search_node(root, elem) ที่ส่วนท้ายของโหนด

• nodes :=ชุดใหม่จากโหนด

• คืนค่า fn(root)

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

import collections
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 print_tree(root):
   if root is not None:
      print_tree(root.left)
      print(root.data, end = ', ')
      print_tree(root.right)
def solve(root, node_list):
   nodes = []
   for elem in node_list:
      nodes.append(search_node(root, elem))
      nodes = set(nodes)
def fn(node):
   if not node:
      return node
   elif node in nodes:
      return node
      left, right = fn(node.left), fn(node.right)
      return node if left and right else left or right
   return fn(root)
root = make_tree([5, 3, 7, 2, 4, 6, 8])
print(solve(root, [6,8]).data)

อินพุต

make_tree([5, 3, 7, 2, 4, 6, 8]), [6, 8]

ผลลัพธ์

7