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).
Objective: Returning the values of nodes in the order of zigzag level order traversal.
Constraints:
1. The number of nodes in the tree is in the range [0, 2000].
2. -100 <= Node.val <= 100
Edge Cases:
1) When the tree is empty
2) When the tree only has one node
3) When the tree has multiple nodes in multiple depths
What is a Zigzag Level Order Traversal?
Zigzag level order traversal reverses the direction of traversal at each depth.
Here is an example input and output of Zigzag Level Order Traversal.
Two Key Elements of Zigzag Level Order Traversal
1. It is Level Order Traversal. We have to traverse the nodes on one depth first in order to get to the next depth.
2. The direction of traversal will reverse for each depth. Even Levels will go from left to right and odds will go in reverse.
We Can Say That:
At Depth 0: the direction of traversal is left to right
At Depth 1: the direction of traversal is right to left
At Depth 2: the direction of traversal is left to right
and so on.
When the direction goes from left to right:
nodes_to_visit: [leftmost node in tree is in the leftmost side of list]
When the direction goes from right to left:
nodes_to_visit: [leftmost node in tree is in the leftmost side of list]
When we are done with each depth:
1. Update the number of nodes in each depth.
2. Append the values list for that depth to the final list of values
3. Re-initialize the values list of depth to be an empty list. Also, update the number of nodes of that level.
It would be easy to say: Why not reverse the list when we append to the result list
Reversing the list will cost around (n/2) assuming that half of the nodes will be reversed. Therefore, it will cause our time complexity to be O(n^2).
How it works:
Read the description above in the brainstorm part of this post!
from collections import dequeue
def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
nodes_to_visit = deque()
final_value_list = []
depth_value_list = []
node = root
nodes_in_level = 1
# Will append children from Right to Left if 1
traversal_direction_LR = 1
while node:
depth_value_list.append(node.val)
# Adding children of Treenode to nodes_to_visit
if traversal_direction_LR == 1:
if node.left:
nodes_to_visit.appendleft(node.left)
if node.right:
nodes_to_visit.appendleft(node.right)
else:
if node.right:
nodes_to_visit.append(node.right)
if node.left:
nodes_to_visit.append(node.left)
# Updating nodes_in_level
nodes_in_level -= 1
# Updating nodes_in_level when done with one depth
if nodes_in_level == 0:
final_value_list.append(depth_value_list)
depth_value_list = []
nodes_in_level = len(nodes_to_visit)
traversal_direction_LR *= -1
# Updating node
if nodes_to_visit:
if traversal_direction_LR == 1:
node = nodes_to_visit.pop()
else:
node = nodes_to_visit.popleft()
else:
node = None
return final_value_list
Limitations:
LeetCode Question #103