Description
Given the root of a binary tree, return the zigzag level order traversal of its nodes' values (i.e., from left to right, then right to left for the next level and alternate).
Examples
Input:
root = [3,9,20,null,null,15,7]Output:
[[3],[20,9],[15,7]]Explanation:
Traverse alternating left-right and right-left.
Input:
root = [1,2,3,4,5,6,7]Output:
[[1],[3,2],[4,5,6,7]]Explanation:
Level 0 has node 1 (left to right). Level 1 has nodes 2,3 but traversing right to left, so [3,2]. Level 2 has nodes 4,5,6,7 and traversing left to right again, so [4,5,6,7].
Input:
root = [5]Output:
[[5]]Explanation:
Single node tree - only one level with one node, so the zigzag traversal contains just [5] at level 0.
Constraints
- •
0 ≤ number of nodes ≤ 2000 - •
-100 ≤ Node.val ≤ 100