文章目录
- 题目
- 标题和出处
- 难度
- 题目描述
- 要求
- 示例
- 数据范围
- 前言
- 解法一
- 思路和算法
- 代码
- 复杂度分析
- 解法二
- 思路和算法
- 代码
- 复杂度分析
- 解法三
- 预备知识
- 思路和算法
- 代码
- 复杂度分析
题目
标题和出处
标题：验证二叉树
出处：1361. 验证二叉树
难度
6 级
题目描述
要求
有n \texttt{n}n个二叉树结点，从0 \texttt{0}0到n − 1 \texttt{n} - \texttt{1}n−1编号，其中结点i \texttt{i}i的两个子结点分别是leftChild[i] \texttt{leftChild[i]}leftChild[i]和rightChild[i] \texttt{rightChild[i]}rightChild[i]。当且仅当所有结点形成恰好一个有效的二叉树时，返回true \texttt{true}true。
如果结点i \texttt{i}i没有左子结点，那么leftChild[i] \texttt{leftChild[i]}leftChild[i]等于-1 \texttt{-1}-1。右子结点也符合该规则。
注意：结点没有值，这道题中仅使用结点编号。
示例
示例 1：
输入：n = 4, leftChild = [1,-1,3,-1], rightChild = [2,-1,-1,-1] \texttt{n = 4, leftChild = [1,-1,3,-1], rightChild = [2,-1,-1,-1]}n = 4, leftChild = [1,-1,3,-1], rightChild = [2,-1,-1,-1]
输出：true \texttt{true}true
示例 2：
输入：n = 4, leftChild = [1,-1,3,-1], rightChild = [2,3,-1,-1] \texttt{n = 4, leftChild = [1,-1,3,-1], rightChild = [2,3,-1,-1]}n = 4, leftChild = [1,-1,3,-1], rightChild = [2,3,-1,-1]
输出：false \texttt{false}false
示例 3：
输入：n = 2, leftChild = [1,0], rightChild = [-1,-1] \texttt{n = 2, leftChild = [1,0], rightChild = [-1,-1]}n = 2, leftChild = [1,0], rightChild = [-1,-1]
输出：false \texttt{false}false
数据范围
- n = leftChild.length = rightChild.length \texttt{n} = \texttt{leftChild.length} = \texttt{rightChild.length}n=leftChild.length=rightChild.length
- 1 ≤ n ≤ 10 4 \texttt{1} \le \texttt{n} \le \texttt{10}^\texttt{4}1≤n≤104
- -1 ≤ leftChild[i], rightChild[i] ≤ n − 1 \texttt{-1} \le \texttt{leftChild[i], rightChild[i]} \le \texttt{n} - \texttt{1}-1≤leftChild[i], rightChild[i]≤n−1
前言
给定的n nn个结点以及左右子结点的关系可以看成有向图。如果有向图的所有结点形成恰好一个有效的二叉树，则应满足以下条件。
边数等于n − 1 n - 1n−1。
只有根结点的入度是0 00，其余n − 1 n - 1n−1个结点的入度都是1 11。
全部结点和边组成连通无环图。
条件 1 和条件 2 可以通过遍历图中的全部边判断。具体而言，对于0 ≤ i < n 0 \le i < n0≤i<n，如果leftChild [ i ] ≥ 0 \textit{leftChild}[i] \ge 0leftChild[i]≥0则存在一条从结点i ii指向结点leftChild [ i ] \textit{leftChild}[i]leftChild[i]的有向边，如果rightChild [ i ] ≥ 0 \textit{rightChild}[i] \ge 0rightChild[i]≥0则存在一条从结点i ii指向结点rightChild [ i ] \textit{rightChild}[i]rightChild[i]的有向边。
遍历全部边之后，如果不满足条件 1 或条件 2，则有向图的所有结点一定不能形成恰好一个有效的二叉树，返回false \text{false}false。当以下情况之一出现时，不满足条件 1 或条件 2。
边数不等于n − 1 n - 1n−1。
不存在入度是0 00的结点，或者有超过1 11个入度是0 00的结点。
存在入度大于1 11的结点。
当条件 1 和条件 2 都满足时，有向图可能由一个二叉树和一个或多个环组成，此时有向图的所有结点不能形成恰好一个有效的二叉树，因此需要判断条件 3 是否满足。由于边数等于结点数少1 11，因此连通图一定无环，只要判断有向图是否连通即可。
可以使用广度优先搜索、深度优先搜索或并查集判断有向图是否连通。
解法一
思路和算法
可以使用广度优先搜索判断有向图是否连通。入度是0 00的结点是根结点，从根结点开始遍历，对于每个结点，如果存在子结点则继续访问子结点。遍历结束时，根据访问的结点数是否等于n nn判断有向图是否连通。
根结点所在的连通分量中一定不存在环，否则会存在入度大于1 11的结点，因此广度优先搜索的过程中不需要记录每个结点是否被访问过。
代码
classSolution{publicbooleanvalidateBinaryTreeNodes(intn,int[]leftChild,int[]rightChild){intedges=0;int[]indegrees=newint[n];for(inti=0;i<n;i++){intleft=leftChild[i],right=rightChild[i];if(left>=0){edges++;indegrees[left]++;}if(right>=0){edges++;indegrees[right]++;}}if(edges!=n-1){returnfalse;}introot=-1;for(inti=0;i<n;i++){if(indegrees[i]==0){if(root<0){root=i;}else{returnfalse;}}elseif(indegrees[i]>1){returnfalse;}}if(root<0){returnfalse;}intvisitCount=0;Queue<Integer>queue=newArrayDeque<Integer>();queue.offer(root);while(!queue.isEmpty()){intnode=queue.poll();visitCount++;intleft=leftChild[node],right=rightChild[node];if(left>=0){queue.offer(left);}if(right>=0){queue.offer(right);}}returnvisitCount==n;}}复杂度分析
时间复杂度：O ( n ) O(n)O(n)，其中n nn是结点数。计算边数和每个结点的入度需要O ( n ) O(n)O(n)的时间，判断每个结点的入度是否符合要求需要O ( n ) O(n)O(n)的时间，广度优先搜索需要O ( n ) O(n)O(n)的时间遍历每个结点最多一次。
空间复杂度：O ( n ) O(n)O(n)，其中n nn是结点数。入度数组和队列需要O ( n ) O(n)O(n)的空间。
解法二
思路和算法
也可以使用深度优先搜索判断有向图是否连通。入度是0 00的结点是根结点，从根结点开始遍历，对于每个结点，如果存在子结点则继续访问子结点。遍历结束时，根据访问的结点数是否等于n nn判断有向图是否连通。
根结点所在的连通分量中一定不存在环，否则会存在入度大于1 11的结点，因此深度优先搜索的过程中不需要记录每个结点是否被访问过。
代码
classSolution{intn;int[]leftChild;int[]rightChild;intvisitCount=0;publicbooleanvalidateBinaryTreeNodes(intn,int[]leftChild,int[]rightChild){this.n=n;this.leftChild=leftChild;this.rightChild=rightChild;intedges=0;int[]indegrees=newint[n];for(inti=0;i<n;i++){intleft=leftChild[i],right=rightChild[i];if(left>=0){edges++;indegrees[left]++;}if(right>=0){edges++;indegrees[right]++;}}if(edges!=n-1){returnfalse;}introot=-1;for(inti=0;i<n;i++){if(indegrees[i]==0){if(root<0){root=i;}else{returnfalse;}}elseif(indegrees[i]>1){returnfalse;}}if(root<0){returnfalse;}dfs(root);returnvisitCount==n;}publicvoiddfs(intnode){visitCount++;intleft=leftChild[node],right=rightChild[node];if(left>=0){dfs(left);}if(right>=0){dfs(right);}}}复杂度分析
时间复杂度：O ( n ) O(n)O(n)，其中n nn是结点数。计算边数和每个结点的入度需要O ( n ) O(n)O(n)的时间，判断每个结点的入度是否符合要求需要O ( n ) O(n)O(n)的时间，深度优先搜索需要O ( n ) O(n)O(n)的时间遍历每个结点最多一次。
空间复杂度：O ( n ) O(n)O(n)，其中n nn是结点数。入度数组和递归调用栈需要O ( n ) O(n)O(n)的空间。
解法三
预备知识
该解法涉及到并查集。
并查集是一种树型的数据结构，用于处理不相交集合的合并与查询问题。
思路和算法
当每个结点的入度都不超过1 11时，根结点所在的连通分量中一定不存在环，且该连通分量一定是有效的二叉树，简单说明如下：对于除了根结点以外的每个结点v vv，一定存在恰好一条指向结点v vv的有向边，将这条有向边的起点记为结点u uu，则结点u uu是结点v vv的父结点，每一对相邻结点之间的父结点和子结点关系形成二叉树。
因此，使用并查集时不需要考虑每条边的方向，只要将每条边连接的两个结点合并即可。
并查集初始化时，n nn个结点分别属于n nn个不同的集合，每个集合只包含一个结点，集合个数等于结点个数。
初始化之后，遍历每条边，将同一条边连接的两个结点所在的集合做合并，每次合并之后将集合个数减1 11。
遍历结束之后，并查集的集合个数即为连通分量数，根据并查集的集合个数是否等于1 11判断有向图是否连通。
代码
classSolution{intn;int[]leftChild;int[]rightChild;intvisitCount=0;publicbooleanvalidateBinaryTreeNodes(intn,int[]leftChild,int[]rightChild){this.n=n;this.leftChild=leftChild;this.rightChild=rightChild;intedges=0;int[]indegrees=newint[n];for(inti=0;i<n;i++){intleft=leftChild[i],right=rightChild[i];if(left>=0){edges++;indegrees[left]++;}if(right>=0){edges++;indegrees[right]++;}}if(edges!=n-1){returnfalse;}introot=-1;for(inti=0;i<n;i++){if(indegrees[i]==0){if(root<0){root=i;}else{returnfalse;}}elseif(indegrees[i]>1){returnfalse;}}if(root<0){returnfalse;}UnionFinduf=newUnionFind(n);for(inti=0;i<n;i++){intleft=leftChild[i],right=rightChild[i];if(left>=0){uf.union(i,left);}if(right>=0){uf.union(i,right);}}returnuf.getCount()==1;}}classUnionFind{privateint[]parent;privateint[]rank;privateintcount;publicUnionFind(intn){parent=newint[n];for(inti=0;i<n;i++){parent[i]=i;}rank=newint[n];count=n;}publicvoidunion(intx,inty){introotx=find(x);introoty=find(y);if(rootx!=rooty){if(rank[rootx]>rank[rooty]){parent[rooty]=rootx;}elseif(rank[rootx]<rank[rooty]){parent[rootx]=rooty;}else{parent[rooty]=rootx;rank[rootx]++;}count--;}}publicintfind(intx){if(parent[x]!=x){parent[x]=find(parent[x]);}returnparent[x];}publicintgetCount(){returncount;}}复杂度分析
时间复杂度：O ( n × α ( n ) ) O(n \times \alpha(n))O(n×α(n))，其中n nn是结点数，α \alphaα是反阿克曼函数。并查集的初始化需要O ( n ) O(n)O(n)的时间，然后遍历n − 1 n - 1n−1条边执行n − 1 n - 1n−1次合并操作，这里的并查集使用了路径压缩和按秩合并，单次操作的时间复杂度是O ( α ( n ) ) O(\alpha(n))O(α(n))，因此并查集初始化之后的操作的时间复杂度是O ( n × α ( n ) ) O(n \times \alpha(n))O(n×α(n))，总时间复杂度是O ( n × α ( n ) ) O(n \times \alpha(n))O(n×α(n))。
空间复杂度：O ( n ) O(n)O(n)，其中n nn是结点数。并查集需要O ( n ) O(n)O(n)的空间。
