Description#
You have n binary tree nodes numbered from 0 to n - 1 where node i has two children leftChild[i] and rightChild[i], return true if and only if all the given nodes form exactly one valid binary tree.
If node i has no left child then leftChild[i] will equal -1, similarly for the right child.
Note that the nodes have no values and that we only use the node numbers in this problem.
Example 1:
Input: n = 4, leftChild = [1,-1,3,-1], rightChild = [2,-1,-1,-1]
Output: true
Example 2:
Input: n = 4, leftChild = [1,-1,3,-1], rightChild = [2,3,-1,-1]
Output: false
Example 3:
Input: n = 2, leftChild = [1,0], rightChild = [-1,-1]
Output: false
Constraints:
n == leftChild.length == rightChild.length1 <= n <= 104-1 <= leftChild[i], rightChild[i] <= n - 1
Solutions#
Solution 1: Union-Find#
We can traverse each node $i$ and its corresponding left and right children $l$, $r$, using an array $vis$ to record whether the node has a parent:
- If the child node already has a parent, it means there are multiple fathers, which does not meet the condition, so we return
false directly. - If the child node and the parent node are already in the same connected component, it means a cycle will be formed, which does not meet the condition, so we return
false directly. - Otherwise, we perform a union operation, set the corresponding position of the $vis$ array to
true, and decrease the number of connected components by $1$.
After the traversal, we check whether the number of connected components in the union-find set is $1$. If it is, we return true, otherwise, we return false.
The time complexity is $O(n \times \alpha(n))$, and the space complexity is $O(n)$. Where $n$ is the number of nodes, and $\alpha(n)$ is the inverse Ackermann function, which is less than $5$.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution:
def validateBinaryTreeNodes(
self, n: int, leftChild: List[int], rightChild: List[int]
) -> bool:
def find(x: int) -> int:
if p[x] != x:
p[x] = find(p[x])
return p[x]
p = list(range(n))
vis = [False] * n
for i, (a, b) in enumerate(zip(leftChild, rightChild)):
for j in (a, b):
if j != -1:
if vis[j] or find(i) == find(j):
return False
p[find(i)] = find(j)
vis[j] = True
n -= 1
return n == 1
|
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
| class Solution {
private int[] p;
public boolean validateBinaryTreeNodes(int n, int[] leftChild, int[] rightChild) {
p = new int[n];
for (int i = 0; i < n; ++i) {
p[i] = i;
}
boolean[] vis = new boolean[n];
for (int i = 0, m = n; i < m; ++i) {
for (int j : new int[] {leftChild[i], rightChild[i]}) {
if (j != -1) {
if (vis[j] || find(i) == find(j)) {
return false;
}
p[find(i)] = find(j);
vis[j] = true;
--n;
}
}
}
return n == 1;
}
private int find(int x) {
if (p[x] != x) {
p[x] = find(p[x]);
}
return p[x];
}
}
|
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
| class Solution {
public:
bool validateBinaryTreeNodes(int n, vector<int>& leftChild, vector<int>& rightChild) {
int p[n];
iota(p, p + n, 0);
bool vis[n];
memset(vis, 0, sizeof(vis));
function<int(int)> find = [&](int x) {
return p[x] == x ? x : p[x] = find(p[x]);
};
for (int i = 0, m = n; i < m; ++i) {
for (int j : {leftChild[i], rightChild[i]}) {
if (j != -1) {
if (vis[j] || find(i) == find(j)) {
return false;
}
p[find(i)] = find(j);
vis[j] = true;
--n;
}
}
}
return n == 1;
}
};
|
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
| func validateBinaryTreeNodes(n int, leftChild []int, rightChild []int) bool {
p := make([]int, n)
for i := range p {
p[i] = i
}
var find func(int) int
find = func(x int) int {
if p[x] != x {
p[x] = find(p[x])
}
return p[x]
}
vis := make([]bool, n)
for i, a := range leftChild {
for _, j := range []int{a, rightChild[i]} {
if j != -1 {
if vis[j] || find(i) == find(j) {
return false
}
p[find(i)] = find(j)
vis[j] = true
n--
}
}
}
return n == 1
}
|
