Chương trình tìm tổng lớn nhất đường đi giữa hai nút trên cây nhị phân trong Python

Cho cây nhị phân, tìm tổng lớn nhất của bất kỳ đường đi nào giữa hai nút bất kỳ (đường đi có thể không qua gốc).

Ví dụ: cây như hình → kết quả 62 (đường đi [12, 13, 14, 16, 7]).

Giải thuật (DFS pós-order - Max Path Sum)

1. Biến toàn cục .
2. Hàm trả về tổng lớn nhất đường đi từ xuống một lá (một nhánh).
3. Tại mỗi nút:
   • , .
   • (tổng nhánh tốt nhất qua nút này).
   • (tổng đường đi qua nút này nối 2 nhánh).
   • Cập nhật .
   • Trả về .
4. Gọi và trả về .

Ví dụ minh họa

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

Đầu vào

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)

Đầu ra

62