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