题解 | #求二叉树的层序遍历#

'''
解题思路：
1、BFS广度优先搜索，先获得每一层需要输出节点的个数，再一个个减小到0，这一层输出结束后，再输出下一层
2、queue.insert(0, cur.left)，新增节点插入到0位
'''
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 
# @param root TreeNode类 
# @return int整型二维数组
#
class Solution:
    def levelOrder(self , root ):
        # write code here        
        if not root:
            return None

        queue = [root]
        res = []
        def bfs(root):
            while queue:
                n = len(queue)
                level = []
                while n>0:
                    cur = queue.pop()
                    level.append(cur.val)
                    if cur.left:
                        queue.insert(0, cur.left)
                    if cur.right:
                        queue.insert(0, cur.right)
                    n -= 1
                res.append(level)
            return res

        return bfs(root)