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).
Given binary tree
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 :)