Traverse a Binary Tree in Zigzag Level Order

Return a binary tree's node values in zigzag level order: the root level is read left to right, the next level right to left, and subsequent levels alternate directions. ### Function Contract Implement `zigzag_levels(values, children) -> list[list[int]]`. `values[i]` is node `i`'s value. The equally sized array `children` contains pairs `[left, right]` of child identifiers, using `-1` for a missing child. If the tree is nonempty, node `0` is the root. Return one inner array per level, from the root downward, in that level's required direction. ### Constraints and Clarifications The array encoding and bounds are explicit practice interface choices. - `0 <= len(values) == len(children) <= 200000`. - Values are integers between `-1000000000` and `1000000000`, inclusive, and may repeat. - The input describes a valid binary tree with all nodes reachable from root `0`, no cycles, and exactly one parent for every nonroot node. - A missing child occupies no output position. - Return `[]` for an empty tree. - Aim for `O(n)` time, excluding no part of the required output construction. ### Examples ```text values = [10, 20, 30, 40, 50] children = [[1, 2], [3, 4], [-1, -1], [-1, -1], [-1, -1]] Output: [[10], [30, 20], [40, 50]] ``` ```text values = [7] children = [[-1, -1]] Output: [[7]] ``` ```hint Separate level membership from display direction First determine which nodes belong to one level. Changing how that level's values are written should not accidentally change which nodes belong to the next level. ```