leetcodesolutions/code/1361.validate-binary-tree-nodes.java at main · Raghuram42/leetcodesolutions · GitHub

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
class Solution {
    int[] parents;
    public boolean validateBinaryTreeNodes(int n, int[] leftChild, int[] rightChild) {
        parents= new int[n];

        Arrays.fill(parents, -1);


        for(int i=0;i<leftChild.length;i++){
            if(leftChild[i] != -1 )
            if(!union(i, leftChild[i]))
                return false;

            if(rightChild[i] != -1 )
            if(!union(i, rightChild[i]))
                return false;
        }

        int c = 0;
        for(int i=0;i<n;i++)
            if(parents[i] == -1)
                c++;
        return c == 1;
    }

    public boolean union(int i, int j){

        int p1 = find(i);
        int p2 = find(j);

        if(p1 == p2)
            return false;

        parents[p1] = p2;
        return true;
    }

    public int find(int i){
        if(parents[i] != -1){
            parents[i] = find(parents[i]);
            return parents[i];
        }

        return i;
    }
}