Zig-Zag Traversal

Problem Statement 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 between). Zigzag traversal of a binary tree is a way of visiting the nodes of the tree in a zigzag pattern, alternating between left to right and right to left at each level. Input Specification The binary tree is represented by a sequence of node values in a level order fashion. A value of 1 indicates a null child. Output Specification Return a list of lists of integers, where each inner list represents the nodes at a specific level in zigzag order. Constraints No explicit constraints on the number of nodes or node values are provided, but assume typical competitive programming limits. Sample Test Cases Example 1: Input: Explanation: The tree structure is: Output: Explanation: Level 1 (Root): Visit the root node 1 from left to right. Output: [1] Level 2: Visit nodes at this level in a right to left order (3 then 2). Output: [3, 2] Level 3: Visit nodes at this level in a left to right order (4, 5 then 6). Output: [4, 5, 6] Example 2: Input: Explanation: The tree structure is: Output: Explanation: Level 1 (Root): Visit the root node 1 from left to right. Output: [1] Level 2: Visit nodes at this level in a right to left order (only 2, as right child of 1 is null). Output: [2] Level 3: Visit nodes at this level in a left to right order (4 then 5). Output: [4, 5] Level 4: Visit nodes at this level in a right to left order (8 then 7). Output: [8, 7]