Python Solution with a queue and two counters (45ms beat 89%)


  • 0
    S

    We know that by doing a BFS, the order in queue is the order by level. The challenge is to know how to separate each level. My solution uses two counters. The first counter records how many pop is needed to reach to the new level so that we could append level[] into final result[]. Another counter to count how many items has been pushed to the queue during the pop we do for this level.

        def levelOrder(self, root):
            """
            :type root: TreeNode
            :rtype: List[List[int]]
            """
            if root is None:
                return []
            queue = deque()
            ret = []
            queue.append(root)
            level = []
            count_this_level = 1
            count_next_level = 0
            while queue:
                n = queue.popleft()
                count_this_level-=1
                if n is not None:
                    level.append(n.val)
                    queue.append(n.left)
                    queue.append(n.right)
                    count_next_level+=2
                if count_this_level == 0:
                    if level:
                        ret.append(level)
                    level=[]
                    count_this_level = count_next_level
                    count_next_level = 0
            
            return ret
    

Log in to reply
 

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