Posted on 2023-10-17 22:00
Uriel 阅读(9)
评论(0) 编辑 收藏 引用 所属分类:
搜索 、
数据结构 、
闲来无事重切Leet Code
给出一颗二叉树节点数量和每个节点的左儿子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