https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal

In this problem we need to traverse binary tree level by level. When we see levels in binary tree, we need to think about bfs, because it is its logic: it first traverse all neighbors, before we go deeper. Here we also need to change direction on each level as well. So, algorithm is the following:

  1. We create queue, where we first put our root.
  2. result is to keep final result and direction, equal to 1 or -1 is direction of traverse.
  3. Then we start to traverse level by level: if we have k elements in queue currently, we remove them all and put their children instead. We continue to do this until our queue is empty. Meanwile we form level list and then add it to result, using correct direction and change direction after.

Complexity: time complexity is O(n), where n is number of nodes in our binary tree. Space complexity is also O(n), because our result has this size in the end. If we do not count output as additional space, then it will be O(w), where w is width of tree. It can be reduces to O(1) I think if we traverse levels in different order directly, but it is just not worth it.

class Solution:
    def zigzagLevelOrder(self, root):
        if not root: return []
        queue = deque([root])
        result, direction = [], 1
        
        while queue:
            level = []
            for i in range(len(queue)):
                node = queue.popleft()
                level.append(node.val)
                if node.left:  queue.append(node.left)
                if node.right: queue.append(node.right)
            result.append(level[::direction])
            direction *= (-1)
        return result

If you like the solution, you can upvote it on leetcode discussion section: Problem 0103