Maximum Level Sum of a Binary Tree

Intuition

Solution

class Solution:
    def maxLevelSum(self, root: TreeNode) -> int:
        if root is None:
            return 0

        queue = collections.deque([])
        ans = 0
        queue.append(root)
        # We use None to split each level
        queue.append(None)

        current = 0
        max_sum = 0
        level = 1
        while queue:
            p = queue.popleft()
            if p is None:
                if not queue:
                    break
                if current > max_sum:
                    max_sum, ans = current, level
                current = 0
                level += 1
                queue.append(None)
                continue
            current += p.val

            if p.left:
                queue.append(p.left)
            if p.right:
                queue.append(p.right)
        return ans