Binary Tree Zigzag Level Order Traversal

Medium- Hard, https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/solution/

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).

During interview:

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]
]

Intuition,

Code BFS using a queue to traverse the tree.

# 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]]:

if not root:
return None

res = []

q = collections.deque()
q.append(root)
level = 0

while q:
nodes_level = []

for _ in range(len(q)):
if level % 2 == 0:
# first root is traversed from left to right
# [node, node siblings from left to right ...]
node = q.popleft()
else:
# # [node siblings from left to right..., node]
node = q.pop()

nodes_level.append(node.val)

if level % 2 == 0:
# root's children will be traversed right to left, so
# we append left to the end of queue first and then append right.
# Children will be inserted [parents' siblings..., left, right]
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
else:
# Children will be inserted [left, right, ...parents' siblings]
if node.right:
q.insert(0, node.right)
if node.left:
q.insert(0, node.left)

level += 1
res.append(nodes_level)

return res

Runtime: 36 ms, faster than 31.74% of Python3 online submissions for Binary Tree Zigzag Level Order Traversal.

Memory Usage: 14.5 MB, less than 32.79% of Python3 online submissions for Binary Tree Zigzag Level Order Traversal.

Complexity Analysis

DFS apprach, the Recursive solution is slightly faster:

class Solution:
def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:
if not root: return
res = []

def traverse(node, level):
if len(res) == level:
res.append(collections.deque())

if level % 2 == 0:
res[level].append(node.val)
else:
res[level].appendleft(node.val)

if node.left: traverse(node.left, level+1)
if node.right: traverse(node.right, level+1)

traverse(root, 0)
return res

Runtime: 28 ms, faster than 88.73% of Python3 online submissions for Binary Tree Zigzag Level Order Traversal.

Memory Usage: 14.6 MB, less than 9.28% of Python3 online submissions for Binary Tree Zigzag Level Order Traversal.

Complexity Analysis

Next Problems to try:

Currently preparing for interviews

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store