题目描述：
$n$ 个节点的二叉树，节点 $i$ 的两个子节点分别为 $leftchild[i], rightchild[i]$ 。如果没有左右节点值等于 $-1$ 。返回能否构成一棵有效的二叉树。
数据范围：
$1\le n \le 10^4$
题解：
使用并查集可以维护连通性，以及求得连通块的数量，判断环。但是还存在一种情况，就是两个点同时指向一个孩子节点，孩子节点的入度为 $2$ ，可以通过记录每个节点的入度判断，也可以通过并查集的性质判断。并查集合并时 $fa[up] = vp$ ，将 $up$ 指向了 $vp$ 。根据这个特点可以将孩子节点指向父节点，每次合并时，查询当前子节点是不是已经有父亲，有父亲则返回 $false$ 。
连通块数量也可以使用两种方法
- 使用 $count$ 记录，初始化为所有节点 $n$ ，每次合并减一。
- 直接在最后判断每个节点的父亲是不是等于自己， $find(i) == i$ ，相等则表明是一个连通块。
代码：
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
| auto optimize_cpp_stdio = []()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
return 0;
}();
class Solution
{
public:
struct UF
{
vector<int> fa;
int count;
UF(int n) : fa(n), count(n)
{
for (int i = 0; i < n; ++i)
fa[i] = i;
}
int find(int u) { return u == fa[u] ? u : fa[u] = find(fa[u]); }
void unite(int u, int v)
{
int up = find(u), vp = find(v);
if (up != vp)
{
fa[up] = vp;
count--;
}
}
bool connect(int u, int v) { return find(u) == find(v); }
int getCount() { return count; }
};
bool validateBinaryTreeNodes(int n, vector<int> &leftChild, vector<int> &rightChild)
{
UF uf(n);
for (int i = 0; i < n; ++i)
{
if (leftChild[i] != -1)
{
if (uf.connect(i, leftChild[i]))
return false;
if (uf.find(leftChild[i]) != leftChild[i])
return false;
uf.unite(leftChild[i], i);
}
if (rightChild[i] != -1)
{
if (uf.connect(i, rightChild[i]))
return false;
if (uf.find(rightChild[i]) != rightChild[i])
return false;
uf.unite(rightChild[i], i);
}
}
if (uf.getCount() != 1)
return false;
return true;
}
};
|