Maximum Level Sum of a Binary Tree

Question in Human Language

In a binary tree, which level has the maximum sum (for ties, the shallow level wins)?

For INHUMAN description, please check it out on LeetCode

Thought No. 1

Hmmm… it seems that we can simply sum up each level and find the maximum by brute force.

Implementation

The steps are:

1. Implement a function that sums up all the elements in a level and output all the nodes in the next level.
2. While the next level nodes outputed by the previous level is not empty.
   1. Use our function to calculate the sum of current level.
   2. Use our function to calculate the nodes in the next level.
   3. Update next level nodes with the output from step 2.2.
   4. Update the global maximum sum and level with the output from step 2.1.
   5. Update the current level ID.
3. Return the global maximum level number.

Python Ver. 1

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def sumNextLevel(self, roots):
        next_roots = []
        lvl_sum = 0
        for r in roots:
            lvl_sum += r.val
            if r.left:
                next_roots.append(r.left)
            if r.right:
                next_roots.append(r.right)
        return next_roots, lvl_sum

    def maxLevelSum(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        next_roots = [root]
        max_sum = 0
        max_lvl = 0
        current_lvl = 0
        while next_roots:
            next_roots, current_sum = self.sumNextLevel(next_roots)
            current_lvl += 1
            if current_sum > max_sum:
                max_sum = current_sum
                max_lvl = current_lvl
        return max_lvl

Review

Well done!