โปรแกรมหาผลรวมเส้นทางยาวที่สุดจากรากถึงใบในต้นไม้ทวิภาคใน Python

สมมติว่าเรามีต้นไม้ทวิภาค หาผลรวมของเส้นทางยาวที่สุดจากรากถึงโหนดใบ ถ้ามีเส้นทางยาวเท่ากันหลายเส้น ให้เลือกเส้นที่มีผลรวมมากกว่า

ตัวอย่าง: จากภาพ ผลลัพธ์ 20

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

1. ฟังก์ชัน rec(curr) คืนค่าคู่ (length, sum):
   • ถ้า curr เป็น None: คืนค่า (0, 0)
   • bigger = max(rec(curr.left), rec(curr.right)) (เปรียบเทียบ length ก่อน แล้วค่อย sum)
   • คืนค่า (bigger[0] + 1, bigger[1] + curr.val)
2. จากเมธอดหลัก เรียก rec(root) คืนค่า index 1 (sum)

ตัวอย่างโค้ด 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):
        def rec(curr):
            if not curr:
                return (0, 0)
            bigger = max(rec(curr.left), rec(curr.right))
            return (bigger[0] + 1, bigger[1] + curr.val)
        return rec(root)[1]

ob = Solution()
root = TreeNode(2)
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))  # Output: 20

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

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

Output: 20