文章目录题目标题和出处难度题目描述要求示例数据范围前言解法一思路和算法代码复杂度分析解法二思路和算法代码复杂度分析解法三预备知识思路和算法代码复杂度分析题目标题和出处标题验证二叉树出处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}nleftChild.lengthrightChild.length1 ≤ 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≤in如果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){intedges0;int[]indegreesnewint[n];for(inti0;in;i){intleftleftChild[i],rightrightChild[i];if(left0){edges;indegrees[left];}if(right0){edges;indegrees[right];}}if(edges!n-1){returnfalse;}introot-1;for(inti0;in;i){if(indegrees[i]0){if(root0){rooti;}else{returnfalse;}}elseif(indegrees[i]1){returnfalse;}}if(root0){returnfalse;}intvisitCount0;QueueIntegerqueuenewArrayDequeInteger();queue.offer(root);while(!queue.isEmpty()){intnodequeue.poll();visitCount;intleftleftChild[node],rightrightChild[node];if(left0){queue.offer(left);}if(right0){queue.offer(right);}}returnvisitCountn;}}复杂度分析时间复杂度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;intvisitCount0;publicbooleanvalidateBinaryTreeNodes(intn,int[]leftChild,int[]rightChild){this.nn;this.leftChildleftChild;this.rightChildrightChild;intedges0;int[]indegreesnewint[n];for(inti0;in;i){intleftleftChild[i],rightrightChild[i];if(left0){edges;indegrees[left];}if(right0){edges;indegrees[right];}}if(edges!n-1){returnfalse;}introot-1;for(inti0;in;i){if(indegrees[i]0){if(root0){rooti;}else{returnfalse;}}elseif(indegrees[i]1){returnfalse;}}if(root0){returnfalse;}dfs(root);returnvisitCountn;}publicvoiddfs(intnode){visitCount;intleftleftChild[node],rightrightChild[node];if(left0){dfs(left);}if(right0){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;intvisitCount0;publicbooleanvalidateBinaryTreeNodes(intn,int[]leftChild,int[]rightChild){this.nn;this.leftChildleftChild;this.rightChildrightChild;intedges0;int[]indegreesnewint[n];for(inti0;in;i){intleftleftChild[i],rightrightChild[i];if(left0){edges;indegrees[left];}if(right0){edges;indegrees[right];}}if(edges!n-1){returnfalse;}introot-1;for(inti0;in;i){if(indegrees[i]0){if(root0){rooti;}else{returnfalse;}}elseif(indegrees[i]1){returnfalse;}}if(root0){returnfalse;}UnionFindufnewUnionFind(n);for(inti0;in;i){intleftleftChild[i],rightrightChild[i];if(left0){uf.union(i,left);}if(right0){uf.union(i,right);}}returnuf.getCount()1;}}classUnionFind{privateint[]parent;privateint[]rank;privateintcount;publicUnionFind(intn){parentnewint[n];for(inti0;in;i){parent[i]i;}ranknewint[n];countn;}publicvoidunion(intx,inty){introotxfind(x);introotyfind(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)的空间。