Given the root of a binary tree, return its values level by level, but alternate the direction: the first level is read left to right, the next right to left, then left to right again, and so on.
- The number of nodes is in the range 0 to 2000
- -100 <= Node.val <= 100
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
Some people try to change the order in which children are pushed into the queue, which quickly becomes confusing and buggy. A cleaner idea: the set of nodes on each level does not change at all, only the order we report them. So run the standard BFS and, on every odd level, fill the level list from the end (or reverse it). Reversing costs O(width) per level, so the total stays O(n).
Algorithm
- Run level order BFS with a queue, tracking a flag
leftToRight = true. - For each level of
sizenodes, create a list of lengthsize. - Put the
i-th popped value at indexiifleftToRight, else at indexsize - 1 - i. - Append the list, flip the flag, and continue.
O(n)Space: O(w), the maximum width of the treeclass Solution: def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]: if not root: return [] res = [] queue = deque([root]) left_to_right = True while queue: size = len(queue) level = [0] * size for i in range(size): node = queue.popleft() # fill from the back on odd levels level[i if left_to_right else size - 1 - i] = node.val if node.left: queue.append(node.left) if node.right: queue.append(node.right) res.append(level) left_to_right = not left_to_right return res