My 46ms easy to understand Python Solution using BFS


  • 0
    E

    The basic idea is to do a breadth first search level by level using a queue. Dequeue the top element from the queue and add it to the current level in the output. Then enqueue its children at the next level.

        def levelOrder(self, root):
            """
            :type root: TreeNode
            :rtype: List[List[int]]
            """
            if not root:
                return []
                
            levels = []
            level = 0
            queue = [(root, level)]
    
            while len(queue) > 0:
                # Add current top of queue to current level in output.
                node, level = queue.pop(0)
                if len(levels) > level:
                    levels[level].append(node.val)
                else:
                    levels.append([node.val])
    
                # Add node's left and right child to queue at next level.
                if node.left:
                    queue.append((node.left, level + 1))
                if node.right:
                    queue.append((node.right, level + 1))
    
            return levels
    

Log in to reply
 

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