Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
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

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理