By: Saurav
2018-01-17 07:44:00 UTC
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).
Example :
Given binary tree
3
/ \
9 20
/ \
15 7
return
[
[3],
[20, 9],
[15, 7]
]
This problem is similar to the problem . We can use BFS similarly as we did in the level order traversal.
1. Use a buffer array to get each level.
2. The only difference being we need to alternate the order of the elements coming from buffer array while adding to the final array
lets see it in work:
def zigzagLevelOrder(a)
return [] unless a
final_array = Array.new
queue = Queue.new
flag = true
buffer_array = Array.new
queue << a
while !queue.empty?
size = queue.size
(size).times do
element = queue.pop
buffer_array << element.data
queue << element.left if element.left
queue << element.right if element.right
end
if flag
final_array << buffer_array
flag = false
else
final_array << buffer_array.reverse
flag = true
end
buffer_array = Array.new
end
return final_array
end
Owned & Maintained by Saurav Prakash
If you like what you see, you can help me cover server costs or buy me a cup of coffee though donation :)