# 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
class Solution:
    def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:
            return []

        ans = []
        this_layer = [root]
        reverse_flag = False

        while this_layer:
            this_layer_ans = []
            next_layer = []
            for node in this_layer:
                this_layer_ans.append(node.val)

                if node.left:
                    next_layer.append(node.left)
                if node.right:
                    next_layer.append(node.right)

            if reverse_flag:
                this_layer_ans.reverse()

            ans.append(this_layer_ans[:]) # deepcopy
            this_layer = next_layer
            reverse_flag = not reverse_flag

        return ans