C++刷leetcode（1361. 验证二叉树）【并查集】【并查集rank优化】
题目描述：二叉树上有 n 个节点，按从 0 到 n - 1 编号，其中节点 i 的两个子节点分别是 leftChild 和 rightChild。
只有 所有 节点能够形成且 只 形成 一颗 有效的二叉树时，返回 true；否则返回 false。
如果节点 i 没有左子节点，那么 leftChild 就等于 -1。右子节点也符合该规则。
注意：节点没有值，本问题中仅仅使用节点编号。
示例 1：
输入：n = 4, leftChild = , rightChild =
输出：true
示例 2：
输入：n = 4, leftChild = , rightChild =
输出：false
示例 3：
输入：n = 2, leftChild = , rightChild = [-1,-1]
输出：false
示例 4：
输入：n = 6, leftChild = , rightChild =
输出：false
提示：
1 <= n <= 10^4
leftChild.length == rightChild.length == n
-1 <= leftChild, rightChild <= n - 1
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/validate-binary-tree-nodes
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
class Solution {
public:
int find_root(int x, vector<int> & father){
if(x != father) return find_root(father, father);
return x;
}
bool uniton(int x, int y, vector<int> & father, vector<int> & rank){
int temp1 = find_root(x, father);
int temp2 = find_root(y, father);
if(temp1 == temp2)return true;
if(rank < rank){
father = temp2;
}else if(rank >= rank){
father = temp1;
if(rank == rank){
rank++;
}
}
return false;
}
bool validateBinaryTreeNodes(int n, vector<int>& leftChild, vector<int>& rightChild) {
vector<int> father(n, 0);
vector<int> rank(n, 0);
for(int i = 0; i < n; i++){
father = i;
rank = 1;
}
for(int i = 0; i < n; i++){
if(leftChild != -1){
if(uniton(i, leftChild, father, rank)) return false;
}
if(rightChild != -1){
if(uniton(i, rightChild, father, rank)) return false;
}
}
set<int> group;
for(int i = 0; i < n; i++){
group.insert(find_root(i, father));
if(group.size() > 1) return false;
}
return true;
}
}; {:10_327:}
页:
[1]