Đường kính và Đường đi có tổng lớn nhất trên cây nhị phân

Mục tiêu kiến thức

• Áp dụng quy hoạch động trên cây (Tree DP) theo thứ tự hậu thứ tự (Post-order Traversal).
• Tính đường kính cây nhị phân: độ dài (số lượng cạnh) của đường đi dài nhất giữa hai nút bất kỳ.
• Tính tổng đường đi lớn nhất (Maximum Path Sum): đường đi liên tục qua các nút liền kề, mỗi nút đi qua tối đa 1 lần, hỗ trợ các nút có giá trị âm.

Mô tả bài toán

Cho cây nhị phân với cấu trúc nút:

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

Viết hàm binary_tree_path_metrics(root: TreeNode | None) -> tuple[int, int]:

• Trả về (diameter, max_path_sum).
• Nếu root là None, trả về (0, 0).
• diameter: Số lượng cạnh trên đường đi dài nhất giữa hai nút bất kỳ trong cây (đường đi này có thể hoặc không đi qua gốc).
• max_path_sum: Tổng lớn nhất của một đường đi bất kỳ (phải chứa ít nhất 1 nút). Nếu cây toàn giá trị âm, trả về giá trị nút lớn nhất (ít âm nhất).

Để kiểm thử thuận tiện, module cần cung cấp thêm hàm: build_tree(values: list) -> TreeNode | None xây dựng cây theo thứ tự tầng (Level-order).

Ràng buộc

• Thời gian chạy tối đa: 1000ms.
• Giới hạn bộ nhớ: 256MB.
• Dữ liệu đầu vào tuân thủ đúng kiểu dữ liệu và miền giá trị được mô tả.