1
class Solution {
2
 public:
3
  int find_parent(vector<int> &parent, int x) {
4
    if (parent[x] == x) return x;
5
    return parent[x] = find_parent(parent, parent[x]);
6
  }
7
  bool validateBinaryTreeNodes(int n, vector<int> &leftChild, vector<int> &rightChild) {
8
    vector<int> parent(n);
9
    for (int i = 0; i < n; i++) {
10
      parent[i] = i;
11
    }
12
    int cnt = 0;
13
    for (int i = 0; i < n; i++) {
14
      int y = find_parent(parent, i);
15
      if (leftChild[i] != -1) {
16
        int x = find_parent(parent, leftChild[i]);
17
        if (x != leftChild[i] || y == x) return false;
18
        parent[leftChild[i]] = y;
19
      }
20
      if (rightChild[i] != -1) {
21
        int x = find_parent(parent, rightChild[i]);
22
        if (x != rightChild[i] || y == x) return false;
23
        parent[rightChild[i]] = y;
24
      }
25
    }
26
    int x = find_parent(parent, 0);
27
    for (int i = 1; i < n; i++) {
28
      if (find_parent(parent, i) != x) return false;
29
    }
30
    return true;
31
  }
32
};