103. Binary Tree Zigzag Level Order Traversal

Problem

Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).

For example:
Given binary tree [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

return its zigzag level order traversal as:

[
  [3],
  [20,9],
  [15,7]
]

Discussion

A problem very similar to 107. Binary Tree Level Order Traversal II. While handling is needed for the zigzag level order.

For tree problems require operations on each level, we use BFS.

Solution

A simple BFS basically solves the problem. And determine the level of the current iteration in the input tree by checking the length of the final result we are updating.

from typing import List

# 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: TreeNode) -> List[List[int]]:
        result = []
        if not root:
            return result

        queue = [root]

        while queue:
            if len(result) % 2 == 0:
                result.append([n.val for n in queue])
            else:
                result.append([n.val for n in queue[::-1]])

            temp = []

            for node in queue:
                if node.left:
                    temp.append(node.left)
                if node.right:
                    temp.append(node.right)

            queue = temp

        return result

Complexity Analysis

• Time Complexity: O(n), as we use BFS to scan all nodes in the tree.
• Space Complexity: O(n), as we use BFS to handle level-wise operations, and numbers of elements cached at each row is bounded by n.