data-structure-and-algorithm/Binary Tree Zigzag Level Order Traversal at main · Achyut08/data-structure-and-algorithm · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
# 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]]:
        bfs = []
        left_to_right = True
        if root is None:
            return bfs
        queue = deque([])
        queue.append(root)
        while len(queue) != 0:
            level_size = len(queue)
            current_level = deque([])
            for i in range(level_size):
                current = queue.popleft()

                if left_to_right:
                    current_level.append(current.val)
                else:
                    current_level.appendleft(current.val)

                if current.left is not None:
                    queue.append(current.left)
                if current.right is not None:
                    queue.append(current.right)
            bfs.append(current_level)
            left_to_right = not left_to_right
        return bfs