1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
|
# 1361. Validate Binary Tree Nodes
from collections import defaultdict
"""
you have n binary trees nodes numbered from 0 to n - 1 where node i has two
children left_child and right_child. return true if any only if all the given
nodes from exactly one valid binary tree. if node i has no left children,
then left_child[i] will equal -1. note that the nodes have no values and that
we only use the node numbers in this problem.
"""
class Solution:
def validateBinaryTreeNodes(self, n, left_child, right_child):
graph = defaultdict(list)
in_degree = [0] * n
for node in range(n):
left, right = left_child[node], right_child[node]
if left != -1:
graph[node].append(left)
in_degree[left] += 1
if right != -1:
graph[node].append(right)
in_degree[right] += 1
root_candidates = [node for node in range(n) if in_degree[node] == 0]
if len(root_candidates) != 1:
return False
root = root_candidates[0]
queue = [root]
seen = set([root])
while queue:
node = queue.pop(0)
if node in graph:
for child in graph[node]:
if child in seen:
return False
seen.add(child)
queue.append(child)
return len(seen) == n
if __name__ == "__main__":
obj = Solution()
print(
obj.validateBinaryTreeNodes(
n=4, left_child=[1, -1, 3, -1], right_child=[2, -1, -1, -1]
)
) # expect: True
print(
obj.validateBinaryTreeNodes(
n=4, left_child=[1, -1, 3, -1], right_child=[2, 3, -1, -1]
)
) # expect: False
print(
obj.validateBinaryTreeNodes(n=2, left_child=[1, 0], right_child=[-1, -1])
) # expect: True
|