[Leetcode][python] 1161: Maximum Level of sum of a binary tree - BFS

• Leetcode: 1161 - Maximum level of sum of a binary tree
• Level: Medium
• Link

Maximum Level Sum of a Binary Tree - LeetCode

My approach

1. Iterate through the tree with a bfs approach
2. For each level, sum up the value of each leaf update to a dictionary
3. Sort the dictionary by the value of each level, and return the smallest level with the biggest sum.

from collections import defaultdict
class Solution:
    
    def maxLevelSum(self, root: TreeNode) -> int:
        q = [(root, 1)]
        cnt = 0
        vals = defaultdict(int)
        vals[1] = root.val

        while q:
            rt, level = q.pop(0)
            if rt.left:
                q.append((rt.left, level + 1))
                vals[level + 1] += rt.left.val
            if rt.right:
                q.append((rt.right, level + 1))
                vals[level + 1] += rt.right.val
        
        sort_orders = sorted(vals.items(), key=lambda x: x[1], reverse=True)
        return sort_orders[0][0]