zigzag_level_order.py

from collections import deque

from pathlib import Path
import sys

sys.path.append(str(Path(__file__).resolve().parent.parent))

from binary_tree import create_binary_tree


class Solution:
    def zigzagLevelOrder(self, root):
        if root is None:
            return []

        result = []
        queue = deque([root])
        starts_left = True

        while queue:
            level_order = deque()

            for _ in range(len(queue)):
                curr_node = queue.popleft()

                if starts_left:
                    level_order.append(curr_node.val)
                else:
                    level_order.appendleft(curr_node.val)

                if curr_node.left:
                    queue.append(curr_node.left)

                if curr_node.right:
                    queue.append(curr_node.right)

            starts_left = not starts_left
            result.append(list(level_order))

        return result

        # Time Complexity: O(n)
        # Space Complexity: O(n)


if __name__ == "__main__":
    solution = Solution()

    root = [3, 9, 20, None, None, 15, 7]
    bt = create_binary_tree(root)
    result = solution.zigzagLevelOrder(bt)
    assert result == [[3], [20, 9], [15, 7]]
    print("Test Case 1 Passed!")
    print(result)