Grokking the Coding Interview: Patterns for Coding Questions

0% completed

​

Solution: Zigzag Traversal

Problem Statement

Given a binary tree, populate an array to represent its zigzag level order traversal. You should populate the values of all nodes of the first level from left to right, then right to left for the next level and keep alternating in the same manner for the following levels.

Example 1:

Example 2:

Constraints:

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

Solution

This problem follows the Binary Tree Level Order Traversal pattern. We can follow the same BFS approach

.....

.....

.....

Like the course? Get enrolled and start learning!
E

eesahk

· a year ago

Can we just do the regular BFS level by level and then reverse at the end of each level?

frontier = deque()
frontier.append(root)
visited = set()
level = 0
while frontier:
    next_frontier = deque()
    curr_level = []
    for curr_node in frontier:
        visited.add(curr_node)
        curr_level.append(curr_node.val)
        if curr_node.left and curr_node.left not in visited:
            next_frontier.append(curr_node.left)
        if curr_node.right and curr_node.right not in visited:
            next_frontier.append(curr_node.right)
      
    if not level % 2 == 0:
		    curr_level = curr_level[::-1]
    result.append(curr_level)
    frontier = next_frontier
    level += 1