Leetcode 102: Binary tree level order traversal

July 23, 2015

Problem statement:

Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).

For example:
Given binary tree {3,9,20,#,#,15,7},

    3
   / \
  9  20
    /  \
   15   7

return its level order traversal as:

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

confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

写代码发现很多问题. 程序要多写, 多练. 背算法可能也是一个途径. 从C++代码, 转化成C#, 犯了几个错. 一下学习到很多C#知识, 感觉不错! 练习6种方法. 

1. Solution 1: (push extra null node in the queue to divide level)

Read the blog:

https://github.com/xiaoxq/leetcode-cpp/blob/master/src/BinaryTreeLevelOrderTraversal.cpp

convert it to C# code:

https://github.com/jianminchen/BTreeLevelOrderTraversal/blob/master/BTreeLevelOrderTraversal.cs

C# code passing leetcode online judge:

https://github.com/jianminchen/BTreeLevelOrderTraversal/blob/master/BTreeLevelOrderTraversal2.cs

Solution 2: (using 3 variables to help queue to do BFS algorithm)

blog:

http://fisherlei.blogspot.ca/2013/01/leetcode-binary-tree-level-order.html

C# code:

https://github.com/jianminchen/BTreeLevelOrderTraversal/blob/master/BTreeLevelOrderTraversal3.cs

Solution 3: DFS algorithm:

blog:

http://fisherlei.blogspot.ca/2013/01/leetcode-binary-tree-level-order.html

C# code:

https://github.com/jianminchen/BTreeLevelOrderTraversal/blob/master/BTreeLevelOrderTraversal4.cs

Solution 4: using two containers for current level, next level 

blog:

http://bangbingsyb.blogspot.ca/2014/11/leetcode-binary-tree-level-order.html

C# code:

https://github.com/jianminchen/BTreeLevelOrderTraversal/blob/master/BTreeLevelOrderTraversal5.cs

Solution 5: one queue and iteratively solution (单个queue的迭代解法)
blog:

http://bangbingsyb.blogspot.ca/2014/11/leetcode-binary-tree-level-order.html

C# code:

https://github.com/jianminchen/BTreeLevelOrderTraversal/blob/master/BTreeLevelOrderTraversal6.cs

Solution 6: one queue and extra node null into queue to mark end of level

blog:

http://bangbingsyb.blogspot.ca/2014/11/leetcode-binary-tree-level-order.html

C# code:

https://github.com/jianminchen/BTreeLevelOrderTraversal/blob/master/BTreeLevelOrderTraversal7.cs

Blogs to read:

1. http://www.jiuzhang.com/solutions/binary-tree-level-order-traversal-ii/

2. http://siddontang.gitbooks.io/leetcode-solution/content/tree/binary_tree_level_order_traversal.html

3. http://blog.csdn.net/ljphhj/article/details/22428939