หาผลคูณของผลรวมใบไม้ในแต่ละระดับของต้นไม้บाइनนารีใน Python

สมมติว่าเรามีต้นไม้บाइनนารี สำหรับแต่ละระดับที่มีใบไม้ ให้หาผลรวมค่าของใบไม้ในระดับนั้น แล้วนำผลรวมทุกระดับมาคูณกัน

เช่น ต้นไม้ตัวอย่าง ระดับ 3 มีใบ 9, ระดับ 4 มีใบ 2,12,5,11 ผลลัพธ์ = 9 × (2+12+5+11) = 270

ขั้นตอนการแก้ปัญหา (Level Order Traversal)

1. ใช้คิว BFS วนระดับต่อระดับ
2. ในแต่ละระดับ ตรวจสอบโหนดที่เป็นใบ (ไม่มีลูก)
3. รวมค่าใบไม้ในระดับนั้น ถ้ามีใบ คูณเข้ากับผลลัพธ์

ตัวอย่างโค้ด Python

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

def isLeaf(root):
    return root.left is None and root.right is None

def find_res(root):
    if not root:
        return 0
    res = 1
    que = [root]
    while True:
        level_size = len(que)
        if level_size == 0:
            break
        level_sum = 0
        found_leaf = False
        for _ in range(level_size):
            node = que.pop(0)
            if isLeaf(node):
                found_leaf = True
                level_sum += node.data
            if node.left:
                que.append(node.left)
            if node.right:
                que.append(node.right)
        if found_leaf:
            res *= level_sum
    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))

อินพุต

Binary tree structure as described

เอาต์พุต

270