Binary Tree Zigzag Level Order Traversal LeetCode solution in Python

1
class Solution(object):
2
    def zigzagLevelOrder(self, root):
3
        """
4
        :type root: TreeNode
5
        :rtype: List[List[int]]
6
        """
7
        if not root:
8
            return []
9

10
        ans = []
11

12
        node = root
13

14
        q = collections.deque([node])
15

16
        order = -1
17

18
        while q:
19
            order = -order
20
            level = []
21
            for _ in range(len(q)):
22
                node = q.popleft()
23

24
                level.append(node.val)
25

26
                if node.left:
27
                    q.append(node.left)
28
                if node.right:
29
                    q.append(node.right)
30

31
            ans.append(level[::order])
32

33
        return ans