N叉树层序遍历,输出时每一层的节点值要分开存,例如
Input: root = [1,null,3,2,4,null,5,6]
Output: [[1],[3,2,4],[5,6]]
方法一:BFS,开一个list保存每次进队的头节点,另开一个list保存该头节点对应的层高
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里面的所有头节点,把这些头节点的所有儿子节点都入队,同时把这一批头节点的对应值append到输出list,耗时比方法一少一点
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