Given the root of a binary tree, return its levels as a list of lists where the first level is read left to right, the second right to left, the third left to right, and so on.
Examples
3
/ \
9 20
/ \
15 7
Input: root = build_tree([3, 9, 20, None, None, 15, 7])
Output: [[3], [20, 9], [15, 7]]
Input: root = build_tree([1, 2, 3, 4, None, None, 5])
Output: [[1], [3, 2], [4, 5]]
Constraints
0 <= number of nodes <= 2000-10**4 <= node.val <= 10**4- Target complexity: O(n) time.
Goals
- Alternate the direction of every level
- Track the level index while doing BFS
- Keep the queue itself in normal left-to-right order