class Solution:

    def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:

        if root == None: return []

        ans = [[root.val]]

        cq = [root]

        nq = []

        for i in range(1,2001):

            if len(cq) == 0: break

            ans.append([])

            while cq:

                cur = cq.pop()

                zig = i&1

                nxt = [cur.left, cur.right]

                if nxt[zig] != None:

                    ans[i].append(nxt[zig].val)

                    nq.append(nxt[zig])

                if nxt[1-zig] != None:

                    ans[i].append(nxt[1-zig].val)

                    nq.append(nxt[1-zig])

            cq, nq = nq, []

        return ans[:-1]

그냥 BFS 돌았는데 뭔가 왔다갔다하기가 귀찮네;;

순서가 지그재그라 deque 대신 그냥 list를 stack으로 사용