1361. Validate Binary Tree Nodes
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.length
1 <= 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 |
|
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 |
|
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 |
|