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

สมมติว่าเรามีต้นไม้ทวิภาค และตัวเลข a, b หาค่าของโหนดต่ำสุด (lowest) ที่มี a และ b เป็นลูกหลาน (descendant) โหนดถือเป็นลูกหลานของตัวเองได้

ตัวอย่าง: จากภาพ a = 6, b = 2 ผลลัพธ์ 4

ขั้นตอนการแก้ปัญหา

1. เมธอด solve(root, a, b):
   • ถ้า root เป็น None: คืนค่า -1
   • ถ้า root.val เป็น a หรือ b: คืนค่า root.val
   • left = solve(root.left, a, b)
   • right = solve(root.right, a, b)
   • ถ้า left != -1 และ right != -1: คืนค่า root.val
   • คืนค่า left ถ้า left != -1 มิฉะนั้น right

ตัวอย่างโค้ด Python

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))  # Output: 4

อินพุต / เอาต์พุต

Input: ต้นไม้ตามโค้ดตัวอย่าง, 6, 2

Output: 4