LC 0103 [M] Binary Tree Zigzag Level Order Traversal - ALawliet/algorithms GitHub Wiki

toggle a left-to-right flag for each level

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:
        if not root: return []

        res = []
        Q = deque([root])
        ltr = True

        while Q:
            level = []

            for _ in range(len(Q)):
                node = Q.popleft()

                level.append(node.val)
  
                if node.left:
                    Q.append(node.left)
                if node.right:
                    Q.append(node.right)

            if not ltr: level.reverse()
            res.append(level)
            ltr = not ltr

        return res

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:
        if not root: return []

        res = []
        Q = deque([root])
        ltr = True

        while Q:
            level_size = len(Q)
            level = deque()

            for _ in range(level_size):
                node = Q.popleft()

                # if ltr: level.append(node.val) # or
                # else: level.appendleft(node.val)

                level.append(node.val)
  
                if node.left:
                    Q.append(node.left)
                if node.right:
                    Q.append(node.right)

            level = list(level)

            if not ltr: level.reverse() # or
            
            res.append(level)
            ltr = not ltr

        return res