LintCode|LintCode 69. 二叉树的层次遍历 LintCode69.二叉树的层次遍历

题目描述给出一棵二叉树，返回其节点值的层次遍历（逐层从左往右访问）

首个数据为根节点，后面接着是其左儿子和右儿子节点值，"#"表示不存在该子节点；
节点数量不超过20

测试样例

输入：{1,2,3}
【LintCode|LintCode 69. 二叉树的层次遍历】输出：[[1],[2,3]]
解释：
1
/ \
23
它将被序列化为{1,2,3}
层次遍历

输入：{1,#,2,3}
输出：[[1],[2],[3]]
解释：
1
\
2
/
3
它将被序列化为{1,#,2,3}
层次遍历

思路其实这题有点坑，咋一看还以为要对一个类似于 {1,2,3#,5#,6,#} 这样的输入序列进行处理，其实不是这样的，打开IDE开始撸码的话你就会发现，其实输入的是一个根节点实例，该实例是属于一个TreeNode类型，这个类（不需要自己定义）定义如下：

class TreeNode:
def __init__(self, val):
self.val = val
self.left, self.right = None, None

这样一来就省事多了，用BFS即可解决。
设置一个list，作为tree。
使用一个队列，初始为根节点，循环终止的条件是队列为空，在对队列进行处理前，先记录下当前的长度，代表树中这一层的节点数，即这一次循环队列只弹出这么多个元素。
同时，每次循环都设置一个list，将每个弹出的元素加入到这个list中，代表该层节点。另外，对于弹出的元素，若它的存在左、右儿子，则依次加入到队列，它们将作为下一层节点。
每次循环处理完后都将得到的该层节点list加入到tree这个list中。注意，tree最终是一个包含多个list的list，其中的每个list代表tree的每一level节点。

代码

"""
Definition of TreeNode:
class TreeNode:
def __init__(self, val):
self.val = val
self.left, self.right = None, None
"""
class Solution:
"""
@param root: A Tree
@return: Level order a list of lists of integer
"""
def levelOrder(self, root):
# write your code here
if not root:
return []

tree, queue = [], [root]
self.BFS(tree, queue)

return tree

def BFS(self, t, q):
while q:
# 每一层的节点
level = []
# 当前层的节点数
size_q = len(q)

for _ in range(size_q):
n = q.pop(0)
level.append(n.val)

'''将每层每个节点的左、右孩子加入队列，作为下一层'''
if n.left:
q.append(n.left)

if n.right:
q.append(n.right)

# 得到一层的节点，加入树中
t.append(level)