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

Cho cây nhị phân, tìm tổng lớn nhất của đường đi từ gốc đến lá.

Ví dụ

Cây đầu vào: (hình ảnh).
Đầu ra: 29 (đường 5-9-7-8).

Thuật toán

1. Định nghĩa hàm walk(node, s):
   • Nếu node là None: cập nhật max_sum = max(max_sum, s), trả về.
   • s += node.data.
   • Đệ quy walk(node.left, s) và walk(node.right, s).
2. Khởi tạo max_sum = 0, gọi walk(root, 0).
3. Trả về max_sum.

Mã nguồn Python

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

class Solution:
    def walk(self, node, s):
        if not node:
            self.max_sum = max(self.max_sum, s)
            return
        s += node.data
        self.walk(node.left, s)
        self.walk(node.right, s)
    def solve(self, root):
        self.max_sum = 0
        self.walk(root, 0)
        return self.max_sum

ob = Solution()
root = TreeNode(5)
root.left = TreeNode(1)
root.right = TreeNode(9)
root.right.left = TreeNode(7)
root.right.right = TreeNode(10)
root.right.left.left = TreeNode(6)
root.right.left.right = TreeNode(8)
print(ob.solve(root))

Đầu vào / Đầu ra

Input: root = TreeNode(5) ...
Output: 29