103. Binary Tree Zigzag Level Order Traversal

Problem¶

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

Example 1:

Input: root = [3,9,20,null,null,15,7]
Output: [[3],[20,9],[15,7|3],[20,9],[15,7]]

Example 2:

Input: root = [1]
Output: [[1|1]]

Example 3:

Input: root = []
Output: []

Constraints:

• The number of nodes in the tree is in the range [0, 2000].
• -100 <= Node.val <= 100

Solve¶

Order Traversal and modify on the result¶

O(n)

By reusing our 102. Binary Tree Level Order Traversal, we can just reverse the order of result array at every odd index.

As the order of result is already left -> right

class Solution:
    def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        result = []

        q = []
        if root:
            q.append((root,0))

        while len(q) > 0:
            r, level = q.pop(0)

            if len(result) - 1 < level:
                result.append([])

            result[level].append(r.val)
            if r.left:
                q.append((r.left, level + 1))
            if r.right:
                q.append((r.right, level + 1))

        for i in range(1, len(result), 2):
            result[i] = result[i][::-1]
        return result