Python3 solution with linear time and space

  • 0

    BFS provides just the order we want, and in order to detect the level
    transitions we just store the current level of each node.

    from collections import deque
    class Solution:
        def levelOrder(self, root):
            ans = []
            queue = deque()
            if root:
                queue.append((root, 0))
            prev_level = -1
            visited = set()
            while queue:
                node, level = queue.popleft()
                if level != prev_level:
                    prev_level = level
                for child in (node.left, node.right):
                    if child and child not in visited:
                        queue.append((child, level+1))
            return ans

Log in to reply

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