# 429. N-ary Tree Level Order Traversal N 叉树的层序遍历

@TOC

## # 题目描述

Given an n-ary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).

For example, given a `3-ary` tree:

We should return its level order traversal:

``````[
[1],
[3,2,4],
[5,6]
]
``````

Note:

1. The depth of the tree is at most 1000.
2. The total number of nodes is at most 5000.

N叉树的层次遍历。

## # 解题方法

### # 方法一：BFS

``````"""
# Definition for a 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]]
"""
if not root:
return []
queue = [(root, 0)]
res = [[]]
while queue:
node, level = queue.pop(0)
if level >= len(res):
res.append([])
res[level].append(node.val)
for child in node.children:
queue.append((child, level + 1))
return res
``````

``````"""
# Definition for a 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]]
"""
res = []
que = collections.deque()
que.append(root)
while que:
level = []
size = len(que)
for _ in range(size):
node = que.popleft()
if not node:
continue
level.append(node.val)
for child in node.children:
que.append(child)
if level:
res.append(level)
return res
``````

### # 方法二：DFS

``````"""
# Definition for a 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]]
"""
res = []
self.getLevel(root, res, 0)
return res

def getLevel(self, root, res, level):
if not root:
return []
if level == len(res):
res.append([])
res[level].append(root.val)
for child in root.children:
self.getLevel(child, res, level + 1)
return res
``````

## # 参考资料

637. Average of Levels in Binary Treeopen in new window

## # 日期

2018 年 7 月 12 日 —— 天阴阴地潮潮，已经连着两天这样了 2018 年 11 月 ９ 日 —— 睡眠可以