Zigzag level order
Read a binary tree one level at a time (a level is all the nodes at the same distance from the root; the root is level 1, its children level 2), switching direction at every level: the root's level left to right, the next level right to left, the one after that left to right again, and so on.
Your function gets the tree's root. Return a list with one inner list per level, from the top down, each written in its own direction. An empty tree (root is None) gives [].
Trees in the examples are written in level order, the way build_tree reads them: the root, then each row from left to right, with None where a child is missing.
root = [1, 2, 3, 4, 5, 6, 7]Output[[1], [3, 2], [4, 5, 6, 7]]Level 1 reads left to right, level 2 right to left, and level 3 left to right again.
root = [5, 8, 1, None, 3, 2, None, 9, 4]Output[[5], [1, 8], [3, 2], [4, 9]]From left to right the levels are [5], [8, 1], [3, 2] and [9, 4]. Levels 2 and 4 are read right to left.
root = []Output[]No nodes, so no levels.
0 ≤ number of nodes ≤ 1.3 × 105
-104 ≤ node value ≤ 104
The tree is at most 500 levels deep, so a recursive solution fits under plain Python's default of about 1,000 nested calls.
Plan it first
Write a line for each before you code, then say them out loud. Compare with the Approach tab afterwards.