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

values = [10, 20, 30, 40, 50]
children = [[1, 2], [3, 4], [-1, -1], [-1, -1], [-1, -1]]
Output: [[10], [30, 20], [40, 50]]

values = [7]
children = [[-1, -1]]
Output: [[7]]