Binary Tree Zigzag Level Order Traversal

from collections import deque


def zigzagLevelOrder(root):
    n = len(root)
    levels = []
    queue = deque([0])  # node indexes; the root is never empty
    while queue:
        row = []
        for _ in range(len(queue)):  # exactly the nodes of the current level
            i = queue.popleft()
            row.append(root[i])
            for child in (2 * i + 1, 2 * i + 2):
                if child < n and root[child] != -1:
                    queue.append(child)
        if len(levels) % 2 == 1:  # levels 1, 3, 5, ... read from right to left
            row.reverse()
        levels.append(row)
    return levels

def zigzagLevelOrder(root):
    n = len(root)
    levels = []
    current = [0]  # a stack of node indexes; the root is never empty
    left_to_right = True
    while current:
        row = []
        upcoming = []  # the next level, pushed while this one pops
        while current:
            i = current.pop()
            row.append(root[i])
            # Push so that the next level pops out in its own direction.
            if left_to_right:
                children = (2 * i + 1, 2 * i + 2)
            else:
                children = (2 * i + 2, 2 * i + 1)
            for child in children:
                if child < n and root[child] != -1:
                    upcoming.append(child)
        levels.append(row)
        current = upcoming
        left_to_right = not left_to_right
    return levels