# 1361. Validate Binary Tree Nodes
###### tags: `Leetcode` `FaceBook` `Medium` `Binary Tree`
Link: https://leetcode.com/problems/validate-binary-tree-nodes/
## 思路 $O(N)$ $O(N)$
需要注意的是root不一定是0，所以要通过算有几条边lead to这个node，来找root，在这个过程中我们可以判断出有没有**自己连着自己的loop**，还有是否**有multiple roots**以及**是不是没有root**
接下来找到root之后，可以通过dfs/bfs+visited array来看**有没有circle**，还有一种情况是**有isolated circle**，检查方法就是最后看是不是还有node没有被visited
## Code

class Solution {
    public boolean validateBinaryTreeNodes(int n, int[] leftChild, int[] rightChild) {
        //calculate degree: how many edges lead to this node
        int[] degree = new int[n];
        for(int i = 0;i < n;i++){
            if(leftChild[i]!=-1){
                //self-loop
                if(leftChild[i]==i) return false;
                degree[leftChild[i]]++;
                if(degree[leftChild[i]]>1) return false;
            }
            if(rightChild[i]!=-1){
                //self-loop
                if(rightChild[i]==i) return false;
                degree[rightChild[i]]++;
                if(degree[rightChild[i]]>1) return false;
            }
        }
        //check multiple roots and find root
        int root = -1;
        for(int i = 0;i < n;i++){
            //multiple roots
            if(root!=-1 && degree[i]==0) return false;
            if(degree[i]==0) root = i;
        }
        //no root
        if(root==-1) return false;
        //check circle
        boolean[] visited = new boolean[n];
        Queue<Integer> q = new LinkedList<>();
        q.add(root);
        visited[root] = true;
        while(!q.isEmpty()){
            int curr = q.poll();
            int left = leftChild[curr];
            int right = rightChild[curr];
            if(left!=-1){
                if(visited[left]) return false;
                visited[left] = true;
                q.add(left);
            }
            if(right!=-1){
                if(visited[right]) return false;
                visited[right] = true;
                q.add(right);
            }
        }
        //isolated circle
        //[1,0,3,-1][-1,-1,-1,-1]
        for(int i = 0;i < n;i++){
            if(!visited[i]) return false;
        }
        return true;
    }
}