Python BFS, using deque to handle the zigzag


  • 0

    Using append() and appendleft() to handle the zigzag.

    from collections import deque
    class Solution(object):
        def zigzagLevelOrder(self, root):
            """
            :type root: TreeNode
            :rtype: List[List[int]]
            """
            if not root: return []
            left, level, res = True, 0, []
            queue = deque([(root, level)])
            while queue:
                node, newlevel = queue.popleft()
                if newlevel != level or newlevel == 0:
                    res.append(deque([]))
                    left = not left
                if left:
                    res[newlevel].appendleft(node.val)
                else:
                    res[newlevel].append(node.val)
                if node.left: queue.append((node.left, newlevel + 1))
                if node.right: queue.append((node.right, newlevel + 1))
                level = newlevel
            return [list(i) for i in res]
    

Log in to reply
 

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