The problem
Return a tree’s values level by level, but alternate direction: left-to-right, then right-to-left, and so on.
Input: [1, 2, 3, 4, 5, 6, 7] Output: [[1], [3, 2], [4, 5, 6, 7]]
Picture it
Picture a family photo read like a snake: the first row left to right, the next row right to left. We do a normal level-by-level walk and simply reverse every other row.
Short version: the full lesson (brute force, complexity, edge cases and a quiz) is still being written. The animation is complete.
The key idea
BFS by level; reverse odd levels. O(n).
Python solution
def level_order(root):
if not root:
return []
q, out = deque([root]), []
while q:
level = []
for _ in range(len(q)):
node = q.popleft()
level.append(node.val)
if node.left: q.append(node.left)
if node.right: q.append(node.right)
out.append(level if len(out) % 2 == 0 else level[::-1])
return outLeetCode adds the imports for you. To run this on your own machine, put this at the top: from collections import deque
In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.