[Python] Clean BFS solution, explained
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
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:\n\n1. We create **queue**, where we first put our root.\n2. `result` is to keep final result and `direction`, equal to `1` or `-1` is direction of traverse.\n3. 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.\n\n**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.\n\n```\nclass Solution:\n    def zigzagLevelOrder(self, root):\n        if not root: return []\n        queue = deque([root])\n        result, direction = [], 1\n        \n        while queue:\n            level = []\n            for i in range(len(queue)):\n                node = queue.popleft()\n                level.append(node.val)\n                if node.left:  queue.append(node.left)\n                if node.right: queue.append(node.right)\n            result.append(level[::direction])\n            direction *= (-1)\n        return result\n```\n\nIf you have any questoins, feel free to ask. If you like the solution and explanation, please **upvote!**
['Breadth-First Search']