You're given the root of a binary tree. Return the zigzag level order traversal of its node values. That means the first level goes left-to-right, the second goes right-to-left, the third goes left-to-right again, and so on. Amazon asks BFS variants like this to test level-order traversal with twist logic.
For root = [3, 9, 20, null, null, 15, 7], you'd return [[3], [20, 9], [15, 7]]. Notice level is reversed compared to standard BFS.
Before reading on, think about this: if you already know how to do level-order traversal, what's the smallest change you'd make to alternate directions?