Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
给出一颗二叉树节点数量和每个节点的左儿子label集合以及右儿子label集合,问是否是一颗二叉树,先用set选出root然后BFS,如果同一个节点访问不止一次或者有节点访问不到,则不是二叉树


 1 #1361
 2 #Runtime: 224 ms (Beats 92.11%)
 3 #Memory: 15.5 MB (Beats 71.5%)
 4 
 5 class Solution(object):
 6     def validateBinaryTreeNodes(self, n, leftChild, rightChild):
 7         """
 8         :type n: int
 9         :type leftChild: List[int]
10         :type rightChild: List[int]
11         :rtype: bool
12         """
13         rt = 0
14         child_nodes = set(leftChild + rightChild)
15         for i in xrange(n):
16             if i not in child_nodes:
17                 rt = i
18         vis = set()
19         q = deque([rt])
20         while q:
21             node = q.popleft()
22             if node in vis:
23                 return False
24             vis.add(node)
25             if leftChild[node] != -1:
26                 q.append(leftChild[node]) 
27             if rightChild[node] != -1:
28                 q.append(rightChild[node])
29         return len(vis) == n

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