# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

def solve(node, level, res):
    if not node:
        return
    try:
        res[level].append(node.val)
    except IndexError:
        res.append([node.val])

    solve(node.left, level + 1, res)
    solve(node.right, level + 1, res)


class Solution:
    def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:
        res = []
        solve(root, 0, res)

        for i, arr in enumerate(res):
            if i % 2:
                res[i] = arr[::-1]
        return res