ข้อ 40 · LC1161 Maximum Level Sum of a Binary Tree (ชั้นผลรวมมากสุด) 🟡

# LeetCode ให้ class นี้มาให้แล้ว ที่เขียนไว้ตรงนี้เพื่อให้บล็อกนี้รันได้เองทั้งก้อน
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


from collections import deque

def maxLevelSum(root):
    best_sum = float('-inf')   # ผลรวมมากสุดที่เจอ (เริ่ม -inf กันค่าติดลบ)
    best_level = 1             # เลขชั้นที่ให้ผลรวมมากสุด
    level = 0
    queue = deque([root])
    while queue:
        level += 1            # ขึ้นชั้นใหม่
        size = len(queue)
        total = 0
        for _ in range(size):
            node = queue.popleft()
            total += node.val         # บวกทุก node ในชั้นนี้
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        if total > best_sum:          # เจอชั้นที่รวมมากกว่าเดิม
            best_sum = total
            best_level = level
    return best_level

# ต้นไม้ [1, 7, 0, 7, -8, null, null]
root = TreeNode(1, TreeNode(7, TreeNode(7), TreeNode(-8)), TreeNode(0))
print(maxLevelSum(root))