题目地址：

https://leetcode.com/problems/validate-binary-tree-nodes/

给定一个有向图，并且每个顶点的出度不超过$2$，判断其是否是二叉树。

它是二叉树的条件是以下这么几个： 1、其作为无向图是没有环的； 2、其作为无向图是连通的； 3、只有一个入度为$0$的点。

必要性显然。充分性可以用数学归纳法来做。如果图只有一个顶点，显然。如果图有$n$个顶点，首先找到那个入度为$0$的顶点$r$，由于图连通，所以这个顶点一定有出边，取其出边指向的顶点$u$，如果$u$的入度不为$1$，那么顺着$u$的入边向上找，总能找到另一个入度为$0$的点，这样就矛盾了。所以$u$的入度一定为$1$。现在将这条边断开，由于图连通，所以就形成了两个连通分支，含$u$的那个仍然满足三个条件，由归纳假设知道，其是一棵二叉树。这样就证明了$r$的左右顶点都是二叉树的树根，证明结束。

三个条件中，第一、二点可以用并查集来做，第三点可以开一个数组统计每个顶点的入度，最后数一下即可。代码如下：

public class Solution { class UnionFind { private int[] parent; // 记录连通块的数量 private int group; public UnionFind(int n) { parent = new int[n]; for (int i = 0; i < n; i++) { parent[i] = i; } group = n; } public int find(int x) { if (x != parent[x]) { parent[x] = find(parent[x]); } return parent[x]; } // 合并x和y所在的集合。如果发现了环则返回false，否则返回true public boolean union(int x, int y) { int px = find(x), py = find(y); if (px == py) { return false; } parent[px] = py; group--; return true; } public int getGroup() { return group; } } public boolean validateBinaryTreeNodes(int n, int[] leftChild, int[] rightChild) { int[] count = new int[n]; UnionFind uf = new UnionFind(n); int len = leftChild.length; for (int i = 0; i < len; i++) { int left = leftChild[i], right = rightChild[i]; if ((left != -1 && !uf.union(left, i)) || (right != -1 && !uf.union(right, i))) { return false; } if (left != -1) { count[left]++; } if (right != -1) { count[right]++; } } // 如果连通块个数不等于1，则返回false if (uf.getGroup() != 1){ return false; } // 数一下入度为0的点有多少个 int rootNum = 0; for (int c : count) { if (c == 0) { rootNum++; } } return rootNum == 1; } }

时间复杂度$O(n{\log }^{\ast }n)$，空间$O(n)$。