โปรแกรมหาบรรพบุรุษซึ่งเป็นเรื่องธรรมดาของสององค์ประกอบในไบนารีทรีใน Python

สมมติว่าเรามีไบนารีทรี และเรายังมีตัวเลขสองตัว a และ b เราต้องหาค่าของโหนดต่ำสุดที่มี a และ b เป็นลูกหลาน เราต้องจำไว้ว่าโหนดสามารถเป็นลูกหลานของตัวเองได้

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

a =6, b =2 แล้วผลลัพธ์จะเป็น 4

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

• กำหนดวิธีการแก้ปัญหา () ซึ่งจะเริ่มต้นและ a, b

• ถ้ารูทเป็นโมฆะ

  • กลับ -1

• ถ้าค่าของรูทเป็น a หรือ b แล้ว

  • ส่งคืนค่ารูท

• ซ้าย :=แก้ (ซ้ายของรูท, a, b)

• ขวา :=แก้ (ทางขวาของรูท, a, b)

• ถ้าซ้ายหรือขวาไม่ใช่ -1 แล้ว

  • ส่งคืนค่ารูท

• กลับซ้ายถ้าซ้ายไม่เหมือนกับ -1 มิฉะนั้นทางขวา

• จากเมธอดหลัก เรียก Solve(root)

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

ตัวอย่าง

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