1. Phân tích bài toán và những điểm mấu chốt

Bài toán yêu cầu tìm tổng giá trị lớn nhất của một đường đi trong cây nhị phân. Theo định nghĩa, một đường đi là một chuỗi các nút trong đó mỗi cặp nút liên tiếp đều có cạnh nối và mỗi nút chỉ xuất hiện tối đa một lần. Điều này dẫn đến hai đặc điểm quan trọng:

• Điểm bắt đầu và kết thúc tự do: Đường đi có thể nằm hoàn toàn ở một nhánh, không nhất thiết phải đi qua nút gốc (root).
• Không phân nhánh: Một đường đi khi đi qua một nút N chỉ có thể kết nối tối đa hai nút lân cận. Nghĩa là tại N, đường đi có thể đi từ cha xuống một con, hoặc đi từ con trái qua N rồi sang con phải. Nó không thể cùng lúc đi qua cả cha, con trái và con phải (vì như vậy sẽ tạo thành hình chữ T, không còn là một đường đơn).

2. Chiến lược giải quyết: Đệ quy hậu thứ tự (Post-order DFS)

Để giải quyết bài toán hiệu quả trong một lần duyệt cây, chúng ta cần phân biệt rõ hai khái niệm tại mỗi nút:

Giá trị đóng góp (Contribution)

Đây là giá trị lớn nhất mà một nút có thể cung cấp cho nút cha của nó. Vì đường đi không được phân nhánh, nút cha chỉ có thể chọn một trong hai hướng: hoặc là đi xuống nhánh trái, hoặc là đi xuống nhánh phải của nút hiện tại. Công thức tính giá trị đóng góp của nút node là:

node.val + max(0, đóng_góp_nhánh_trái, đóng_góp_nhánh_phải)

Nếu đóng góp từ các nhánh con là số âm, chúng ta sẽ bỏ qua nhánh đó (coi như bằng 0) để tránh làm giảm tổng giá trị.

Tổng đường đi cực đại tại nút (Bridge Sum)

Tại mỗi nút, chúng ta cũng xem xét trường hợp nút đó đóng vai trò là "đỉnh" của con đường (nối nhánh trái và nhánh phải lại với nhau). Tổng này sẽ là:

node.val + đóng_góp_nhánh_trái + đóng_góp_nhánh_phải

Giá trị này sẽ được dùng để cập nhật biến kết quả toàn cục nhưng không thể trả về cho nút cha vì nó đã bao gồm cả hai nhánh.

3. Triển khai mã nguồn với Python 3

Dưới đây là cách cài đặt sử dụng phương pháp đệ quy, tối ưu hóa bộ nhớ và thời gian chạy:

from typing import Optional

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

class Solution:
    def maxPathSum(self, root: Optional[TreeNode]) -> int:
        # Khởi tạo giá trị nhỏ nhất có thể
        self.best_total = float('-inf')

        def calculate_gain(node: Optional[TreeNode]) -> int:
            if not node:
                return 0
            
            # Tính toán đóng góp từ hai phía. 
            # Nếu giá trị âm, ta gán bằng 0 (không chọn đường đó).
            left_gain = max(calculate_gain(node.left), 0)
            right_gain = max(calculate_gain(node.right), 0)
            
            # Giả định nút hiện tại là đỉnh của đường đi lớn nhất
            # Đường đi này nối từ nhánh trái qua nút hiện tại sang nhánh phải
            current_max_path = node.val + left_gain + right_gain
            
            # Cập nhật kỷ lục toàn cục nếu tìm thấy tổng lớn hơn
            self.best_total = max(self.best_total, current_max_path)
            
            # Trả về giá trị lớn nhất mà node này có thể đóng góp cho node cha
            # Node cha chỉ có thể chọn đi tiếp vào một trong hai nhánh
            return node.val + max(left_gain, right_gain)

        calculate_gain(root)
        return self.best_total

4. Ví dụ minh họa

Giả sử ta có cây nhị phân: [-10, 9, 20, null, null, 15, 7]

• Tại nút 15 và 7: Là nút lá, đóng góp lần lượt là 15 và 7. Kết quả tạm thời best_total = 15.
• Tại nút 20:
  • Đóng góp nhánh trái = 15, nhánh phải = 7.
  • Tổng đường đi "cầu nối" tại đây là: 20 + 15 + 7 = 42. Cập nhật best_total = 42.
  • Giá trị trả về cho nút cha (-10) là: 20 + max(15, 7) = 35.
• Tại nút 9: Đóng góp là 9.
• Tại nút gốc -10:
  • Đóng góp nhánh trái = 9, nhánh phải = 35.
  • Tổng đường đi tại đây là: -10 + 9 + 35 = 34.
  • Vì 34 < 42 nên best_total vẫn giữ nguyên là 42.

5. Đánh giá độ phức tạp

• Độ phức tạp thời gian: O(N), với N là số lượng nút trong cây. Thuật toán duyệt qua mỗi nút đúng một lần theo cơ chế DFS.
• Độ phức tạp không gian: O(H), với H là chiều cao của cây. Đây là không gian lưu trữ trên ngăn xếp (stack) của các lần gọi đệ quy. Trong trường hợp xấu nhất (cây lệch), H có thể bằng N. Trong trường hợp cây cân bằng, H xấp xỉ log(N).

6. Lưu ý quan trọng

• Xử lý số âm: Việc sử dụng max(gain, 0) cực kỳ quan trọng. Nó giúp thuật toán tự động loại bỏ những nhánh cây có tổng giá trị âm, điều này tương đương với việc bắt đầu một đường đi mới tại nút hiện tại.
• Biến toàn cục: Sử dụng self.best_total để theo dõi giá trị lớn nhất xuyên suốt quá trình đệ quy giúp tách biệt giá trị trả về (nhánh đơn) và kết quả cuối cùng (có thể là hình cung).