Chương trình tính tổng các số tạo thành từ đường đi gốc đến lá trong cây nhị phân bằng Python

Cho cây nhị phân mỗi nút chứa chữ số 0-9. Mỗi đường đi từ gốc đến lá tạo thành một số. Tính tổng tất cả các số đó.

Ví dụ: cây cho ra các số 46, 432, 435 → tổng = 913.

Giải thuật

• Đệ quy DFS: hàm solve(root, string) truyền chuỗi số đã xây dựng.
• Nếu gặp lá: trả về int(string + str(root.val)).
• Ngược lại: cộng kết quả từ con trái và con phải (nếu có) với chuỗi mở rộng.

Ví dụ minh họa

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

class Solution:
    def solve(self, root, string=""):
        if root and not root.left and not root.right:
            return int(string + str(root.val))
        total = 0
        if root.left:
            total += int(self.solve(root.left, string + str(root.val)))
        if root.right:
            total += int(self.solve(root.right, string + str(root.val)))
        return total

ob = Solution()
root = TreeNode(4)
root.left = TreeNode(6)
root.right = TreeNode(3)
root.right.left = TreeNode(2)
root.right.right = TreeNode(5)
print(ob.solve(root))

Đầu vào

root = TreeNode(4) ...

Đầu ra

913