103. Binary Tree Zigzag Level Order Traversal.md

103. Binary Tree Zigzag Level Order Traversal

https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/

solution

class Solution:
    def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if root is None:
            return []

        queue = collections.deque([root])
        res = []
        flag = 0

        while queue:
            level = []
            for _ in range(len(queue)):
                node = queue.popleft()
                level.append(node.val)

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

            if flag % 2 == 1:
                level = level[::-1]
            res.append(level)
            flag += 1
        return res

时间复杂度：O(n)
空间复杂度：O(n)