Simple Python BFS (Beats 99.83%, 65ms)

  • 0

    The idea is simple, i.e. to do a level order traversal and compute the max per level and append it to the final answer. The reason this solution is relatively quicker than other solutions is because I try to find max value per level, along with level_nodes for that level in one pass.

    from collections import deque
    _ = float('-inf')
    class Solution(object):
        def largestValues(self, root):
            if root is None:
                return []
            q = deque()
            ans = []
            while len(q) > 0:
                nodes = q.popleft()
                curr_level_nodes = []
                max_val_for_level = _
                for n in nodes:
                    max_val_for_level = max(max_val_for_level, n.val)
                    if n.left:
                    if n.right:
                if curr_level_nodes:
            return ans

  • 0

    The "Beats 99.83%, 65ms" claim isn't true. I just submitted it three times, it got accepted in 76, 96 and 75 ms (beating 83.67%, 34.35% and 86.39%).

  • 0

    @StefanPochmann That's what I got (65ms -- Percentile moved 99.83 to 99.66 probably due to more submissions). Snapshot below. Maybe test cases for the problem aren't large enough to measure run-time accurately.
    0_1497202817127_Screen Shot 2017-06-11 at 10.39.46 AM.png

  • 0

    Update: I submitted second time and got 92ms. Being relatively new to Leetcode I wasn't aware that the run-time shown by Leetcode is not a statistical average over multiple runs.

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.