Chương trình tìm tổng đường đi dài nhất từ gốc đến lá trong cây nhị phân bằng Python

Cho cây nhị phân, tìm tổng của đường đi dài nhất từ gốc đến lá. Nếu có nhiều đường dài bằng nhau, chọn đường có tổng lớn hơn.

Ví dụ: cây cho kết quả 20.

Quy trình giải quyết (Đệ quy)

1. Định nghĩa hàm rec(curr) trả về cặp (độ_dài, tổng) của đường đi dài nhất từ curr đến lá.
2. Nếu curr null, trả về (0, 0).
3. Lấy bigger = max(rec(left), rec(right)) (so sánh theo độ dài, nếu bằng thì theo tổng).
4. Trả về (bigger[0] + 1, bigger[1] + curr.val).
5. Kết quả là phần tử thứ 2 của rec(root).

Ví dụ mã nguồn

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

Đầu vào

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)

Đầu ra

20