Type: Easy, BFS
问题描述：
Given an n-ary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).
给定一个n叉树，返回树的层序遍历的节点值，从左到右，从上到下。
For example, given a 3-ary tree:
img
We should return its level order traversal:
[
[1],
[3,2,4],
[5,6]
]
Note:
- The depth of the tree is at most
1000. - The total number of nodes is at most
5000.
"""
# Definition for a Node.
# Childre是个Node引用数组，
class Node(object):
def __init__(self, val, children):
self.val = val
self.children = children
"""
class Solution(object):
# 层序遍历需要知道知道如何确定一层
def levelOrder(self, root):
"""
:type root: Node
:rtype: List[List[int]]
"""
# 需要记录层序，使用字典结构
que = [[root, 0]]
record = {}
layer = 1
while elements != []:
[cur, layer] = elements.pop(0)
if cur != None:
if layer not in record: # 根据键判断
record[layer] = [cur.val]
else:
record[layer] += [cur.val]
for child in cur.children:
elements += [[child, layer + 1]]
res = [[None]] * len(record)
for key, val in record.items():
res[key - 1] = val
return res
"""
# Definition for a Node.
# Childre是个Node引用数组，
class Node(object):
def __init__(self, val, children):
self.val = val
self.children = children
"""
class Solution(object):
# 层序遍历需要知道知道如何确定一层
def levelOrder(self, root):
"""
:type root: Node
:rtype: List[List[int]]
"""
# 需要记录层序，使用字典结构
que = [[root, 0]]
record = {}
layer = 0
while que != []:
[cur,layer] = que.pop(0)
if cur != None:
if layer not in record:
record[layer] = [cur.val]
else:
record[layer] += [cur.val]
for child in cur.children:
que += [[child, layer + 1]]
res = [[None]] * len(record) # [[None],[None],[None],...]
for key, val in record.items():
res[key] = val # val是个数组
return res
和前面的算法基本一致，这里再拆解一下，简单说，就是用字典来记录树的层的数据，用先进先出的队列来进行遍历。
从根部开始，先加入队列，注意，这里的队列是用数组来模拟的，Python的数组有pop方法，非常好用。
因为是层序输出，所以跟踪层的序号，在将节点加入到队列时，节点的层序也放进来。
一个非常容易犯错的点是，在将已经pop出去的节点的孩子加入队列时，二叉树就是加入左右即可，n叉树需要用一个for循环。注意一定加入的是当前pop出去的孩子节点，是cur.children不是root.children，这个错非常容易犯。
最后，用数组来拿出字典的数值，最后的res = [[None]] * len(record)值得好好看看，并活用。
END.
