Binary Tree Level Order Traversal

Problem description
Level: medium
Given a binary tree, return the level order traversal of its nodes’ values. (ie, from left to right, level by level).

Example
Given binary tree {3,9,20,#,#,15,7},

b1

return its level order traversal as:

[
[3],
[9,20],
[15,7]
]

Challenge
Using only 1 queue to implement it.

Consideration

There are multiple approaches to solve the problem.
1. two queues ( queue 1 save one level, then find nodes for next level, save in to queue 2, then clean queue 1, find next level nodes save them in queue 1)
2. one queue + dummy number (use # as level break, 3 # 9 20 # 15 7)
3. one queue
4. no queue

Solution 1 (no queue)

Solution 2 – one queue

Share on FacebookShare on Google+Tweet about this on TwitterShare on LinkedInShare on RedditShare on StumbleUponEmail this to someoneShare on TumblrDigg this

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code class="" title="" data-url=""> <del datetime=""> <em> <i> <q cite=""> <strike> <strong> <pre class="" title="" data-url=""> <span class="" title="" data-url="">