并查集 如果父节点和子节点已经有共同的祖先，说明会形成环，返回false; 若是子节点已经有父节点了，那直接返回false; 最后判断一下连通分支是不是为1，看看是不是只有一颗树。
class Solution { public: vector<int> p; int N; int f(int i) { while(i!=p[i]) { p[i]=p[p[i]]; i=p[i]; } return i; } bool unio(int a,int b) { if(b==-1)return true; int x=f(a); int y=f(b); if(x==y)return false; if(y==b) {p[b]=a; N--; } else return false; return true; } bool validateBinaryTreeNodes(int n, vector<int>& leftChild, vector<int>& rightChild) { p.resize(n,0); N=n; for(int i=0;i<n;i++) p[i]=i; int i=0; while(i<n) { if(!unio(i,leftChild[i])) return false; if(!unio(i,rightChild[i])) return false; i++; } if(N!=1)return false; return true; } };