Simple Python BFS (Beats 99.83%, 65ms)


  • 0
    P

    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()
            q.append([root])
            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:
                        curr_level_nodes.append(n.left)
                    
                    if n.right:
                        curr_level_nodes.append(n.right)
                
                ans.append(max_val_for_level)
    
                if curr_level_nodes:
                    q.append(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
    P

    @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
    P

    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.