โปรแกรมหาผลรวมสูงสุดของเส้นทางระหว่างสองโหนดในต้นไม้ไบนารีด้วย Python

สมมติว่าเรามีต้นไม้ไบนารี เราต้องการหาผลรวมสูงสุดของเส้นทางระหว่างโหนดใดๆ สองโหนด (Path Sum) เส้นทางอาจผ่านรูทหรือไม่ก็ได้

ตัวอย่างเช่น หากอินพุตเป็นต้นไม้ดังรูป ผลลัพธ์จะเป็น 62 เนื่องจากเส้นทางคือ [12, 13, 14, 16, 7]

ขั้นตอนการแก้ปัญหา (Post-order DFS)

1. สร้างฟังก์ชัน utils(root) คืนค่า max path sum ที่เริ่มจาก root ลงไป:
   • หาก root null ให้คืนค่า 0
   • l = utils(root.left), r = utils(root.right)
   • max_single = max(max(l, r) + root.val, root.val) (เส้นทางตรงไปด้านเดียว)
   • max_top = max(max_single, l + r + root.val) (เส้นทางผ่าน root)
   • อัปเดต res = max(res, max_top)
   • คืนค่า max_single
2. จากเมธอดหลัก: res = -inf, เรียก utils(root), คืนค่า res

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

class TreeNode:
    def __init__(self, value):
        self.val = value
        self.left = None
        self.right = None

class Solution:
    def solve(self, root):
        if root is None:
            return 0
        self.res = float("-inf")
        self.utils(root)
        return self.res
    
    def utils(self, root):
        if root is None:
            return 0
        
        l = self.utils(root.left)
        r = self.utils(root.right)
        
        max_single = max(max(l, r) + root.val, root.val)
        max_top = max(max_single, l + r + root.val)
        
        self.res = max(self.res, max_top)
        return max_single

ob = Solution()
root = TreeNode(13)
root.left = TreeNode(12)
root.right = TreeNode(14)
root.right.left = TreeNode(16)
root.right.right = TreeNode(22)
root.right.left.left = TreeNode(4)
root.right.left.right = TreeNode(7)
print(ob.solve(root))  # Output: 62

อินพุต

root = TreeNode(13)
root.left = TreeNode(12)
root.right = TreeNode(14)
root.right.left = TreeNode(16)
root.right.right = TreeNode(22)
root.right.left.left = TreeNode(4)
root.right.left.right = TreeNode(7)

เอาต์พุต

62