---
title: 1361. Validate Binary Tree Nodes
tags: graph
description: share source code.
---

# 1361. Validate Binary Tree Nodes

class Solution {
    
    static class UnionFind{
        int rank [];
        int parent[];
        int component;
        
        public UnionFind(int n){
            this.rank = new int [n];
            this.parent = new int [n];
            this.component = n;
            
            for(int i = 0; i < n; i++){
                parent[i] = i;
                rank[i] = 1;
            }
        }
        
        public boolean isConnected(int u, int v){
            return find(u) == find(v);
        }
        
        public void merge(int u, int v){
            int pu = find(u);
            int pv = find(v);
            if(rank[pu] < rank[pv]){
                parent[pu] = pv;
            }else if(rank[pu] > rank[pv]){
                parent[pv] = pu;
            }else{
                parent[pv] = pu;
                rank[pu] ++; 
            }
            component --;
        }
        
        public int find(int u){
            while(u != parent[u]){
                parent[u] = parent[parent[u]];
                u = parent[u];
            }
            return u;
        }
        
    }
    
    public boolean validateBinaryTreeNodes(int n, int[] leftChild, int[] rightChild) {
        UnionFind uf = new UnionFind(n);
        int indegrees[] = new int [n];
        for(int i = 0; i < n; i++){
            // 1. union 沒法擋住重複走到的同ㄧ個點 (二個 edge 指向同ㄧ點, union 沒方向), 非 cycle
            // ex: 1 -> 2 <- 3
            // 2. 如果點已經走過 (union 過), 又重複再出現 cycle, return false
            // ex: 1 <-> 2
            // 3. 是否每一個點都 connected
            if(leftChild[i] != -1){
                if(++indegrees[leftChild[i]] == 1 && !uf.isConnected(i , leftChild[i])){
                    uf.merge(i , leftChild[i]);
                }else{
                    return false;
                }
            }
            
            if(rightChild[i] != -1){
                if(++indegrees[rightChild[i]] == 1 &&!uf.isConnected(i , rightChild[i])){
                    uf.merge(i , rightChild[i]);
                }else{
                    return false;
                }
            }

        }
        //System.out.println(uf.component);
        return uf.component == 1 ;
    }
}