N叉樹(shù)層序遍歷，輸出時(shí)每一層的節(jié)點(diǎn)值要分開(kāi)存，例如
Input: root = [1,null,3,2,4,null,5,6]
Output: [[1],[3,2,4],[5,6]]
方法一：BFS，開(kāi)一個(gè)list保存每次進(jìn)隊(duì)的頭節(jié)點(diǎn)，另開(kāi)一個(gè)list保存該頭節(jié)點(diǎn)對(duì)應(yīng)的層高
1 #429
2 #Runtime: 89 ms
3 #Memory Usage: 16.2 MB
4
5 """
6 # Definition for a Node.
7 class Node(object):
8 def __init__(self, val=None, children=None):
9 self.val = val
10 self.children = children
11 """
12
13 class Solution(object):
14 def levelOrder(self, root):
15 """
16 :type root: Node
17 :rtype: List[List[int]]
18 """
19 if not root:
20 return []
21 ans = []
22 q = []
23 q.append(root)
24 p = []
25 p.append(0)
26 pre = 0
27 ans.append([root.val])
28 tp = []
29 while q:
30 if tp and p[0] + 1 > pre:
31 pre = p[0] + 1
32 ans.append(tp)
33 tp = []
34 for i in q[0].children:
35 q.append(i)
36 tp.append(i.val)
37 p.append(p[0] + 1)
38 q.pop(0)
39 p.pop(0)
40 return ans
方法二：BFS，每次直接處理完同一層在queue里面的所有頭節(jié)點(diǎn)，把這些頭節(jié)點(diǎn)的所有兒子節(jié)點(diǎn)都入隊(duì)，同時(shí)把這一批頭節(jié)點(diǎn)的對(duì)應(yīng)值append到輸出list，耗時(shí)比方法一少一點(diǎn)
1 #429
2 #Runtime: 42 ms
3 #Memory Usage: 16.5 MB
4
5 """
6 # Definition for a Node.
7 class Node(object):
8 def __init__(self, val=None, children=None):
9 self.val = val
10 self.children = children
11 """
12
13 class Solution(object):
14 def levelOrder(self, root):
15 """
16 :type root: Node
17 :rtype: List[List[int]]
18 """
19 if not root:
20 return []
21 ans = []
22 q = []
23 q.append(root)
24 ans.append([root.val])
25 while q:
26 q_sz = len(q)
27 tp = []
28 for qq in range(q_sz):
29 for i in q[0].children:
30 q.append(i)
31 tp.append(i.val)
32 q.pop(0)
33 if tp:
34 ans.append(tp)
35 return ans