Posted on 2023-10-17 22:00
Uriel 閱讀(50)
評論(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