Tìm tích các tổng lá theo cấp độ trong cây nhị phân trong Python

Cho cây nhị phân. Với mỗi cấp độ có lá, tính tổng giá trị các lá. Nhân tất cả các tổng này lại.

Ví dụ: cây cho trước → cấp 3 có lá 9, cấp 4 có lá 2,12,5,11 → 9 * (2+12+5+11) = 270.

Giải thuật (BFS theo cấp độ)

• Duyệt cây theo cấp độ (level-order traversal).
• Với mỗi cấp độ: kiểm tra các nút, nếu là lá → cộng vào sum_level, đánh dấu found_leaf.
• Nếu found_leaf: result *= sum_level.
• Trả về result.

Ví dụ

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

def isLeaf(root):
    return not root.left and not root.right

def find_res(root):
    if not root:
        return 0
    res = 1
    que = [root]
    while True:
        no_of_nodes = len(que)
        if no_of_nodes == 0:
            break
        sum_level = 0
        found_leaf = False
        while no_of_nodes > 0:
            curr = que.pop(0)
            if isLeaf(curr):
                found_leaf = True
                sum_level += curr.data
            if curr.left:
                que.append(curr.left)
            if curr.right:
                que.append(curr.right)
            no_of_nodes -= 1
        if found_leaf:
            res *= sum_level
    return res

root = TreeNode(8)
root.left = TreeNode(8)
root.right = TreeNode(6)
root.left.right = TreeNode(7)
root.left.left = TreeNode(9)
root.left.right.left = TreeNode(2)
root.left.right.right = TreeNode(12)
root.right.right = TreeNode(10)
root.right.right.left = TreeNode(5)
root.right.right.right = TreeNode(11)
print(find_res(root))

Đầu vào

Binary tree as constructed

Đầu ra

270