-
Notifications
You must be signed in to change notification settings - Fork 481
/
1361.cpp
42 lines (39 loc) · 1.13 KB
/
1361.cpp
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
class Solution
{
public:
bool validateBinaryTreeNodes(int n, vector<int>& leftChild, vector<int>& rightChild)
{
int d[n] = {};
for (int i : leftChild) if (i != -1) d[i]++;
for (int i : rightChild) if (i != -1) d[i]++;
int root = -1;
for (int i = 0; i < n; i++)
{
if (d[i] == 0)
{
if (root != -1) return false;
root = i;
}
}
if (root == -1) return false;
unordered_set<int> vis = {root};
queue<int> q; q.push(root);
while (!q.empty())
{
int pre = q.front(); q.pop();
if (leftChild[pre] != -1)
{
if (vis.count(leftChild[pre])) return false;
vis.insert(leftChild[pre]);
q.push(leftChild[pre]);
}
if (rightChild[pre] != -1)
{
if (vis.count(rightChild[pre])) return false;
vis.insert(rightChild[pre]);
q.push(rightChild[pre]);
}
}
return vis.size() == n;
}
};