拓扑排序题目：最小高度树

文章目录题目标题和出处难度题目描述要求示例数据范围解法思路和算法代码复杂度分析题目标题和出处标题最小高度树出处310. 最小高度树难度6 级题目描述要求树是一个无向图其中任何两个结点只通过一条路径连接。换句话说任何没有简单环路的连通图都是一个树。给定一个包含n \texttt{n}n个结点的树标记为0 \texttt{0}0到n − 1 \texttt{n} - \texttt{1}n−1以及一个包含n − 1 \texttt{n} - \texttt{1}n−1条无向边的edges \texttt{edges}edges列表其中edges[i] [a i , b i ] \texttt{edges[i] [a}_\texttt{i}\texttt{, b}_\texttt{i}\texttt{]}edges[i] [ai​, bi​]表示树中结点a i \texttt{a}_\texttt{i}ai​和b i \texttt{b}_\texttt{i}bi​之间存在一条无向边。可选择树中任何一个结点作为根。当选择结点x \texttt{x}x作为根结点时设结果树的高度为h \texttt{h}h。在所有可能的树中具有最小高度即min(h) \texttt{min(h)}min(h)的树称为最小高度树。返回所有的最小高度树的根结点标签列表。可以按任意顺序返回答案。树的高度是指根结点和叶结点之间最长向下路径中的边的数量。示例示例 1输入n 4, edges [[1,0],[1,2],[1,3]] \texttt{n 4, edges [[1,0],[1,2],[1,3]]}n 4, edges [[1,0],[1,2],[1,3]]输出[1] \texttt{[1]}[1]解释如图所示当根是标签为1 \texttt{1}1的结点时树的高度是1 \texttt{1}1这是唯一的最小高度树。示例 2输入n 6, edges [[3,0],[3,1],[3,2],[3,4],[5,4]] \texttt{n 6, edges [[3,0],[3,1],[3,2],[3,4],[5,4]]}n 6, edges [[3,0],[3,1],[3,2],[3,4],[5,4]]输出[3,4] \texttt{[3,4]}[3,4]数据范围1 ≤ n ≤ 2 × 10 4 \texttt{1} \le \texttt{n} \le \texttt{2} \times \texttt{10}^\texttt{4}1≤n≤2×104edges.length n − 1 \texttt{edges.length} \texttt{n} - \texttt{1}edges.lengthn−10 ≤ a i , b i n \texttt{0} \le \texttt{a}_\texttt{i}\texttt{, b}_\texttt{i} \texttt{n}0≤ai​, bi​na i ≠ b i \texttt{a}_\texttt{i} \ne \texttt{b}_\texttt{i}ai​bi​所有(a i , b i ) \texttt{(a}_\texttt{i}\texttt{, b}_\texttt{i}\texttt{)}(ai​, bi​)各不相同给定的输入保证是一个树并且不会有重复的边解法思路和算法这道题要求在无向树中寻找所有的最小高度树的根结点可以考虑树中的距离最远的两个结点之间的距离。如果n 1 n 1n1则图中只有一个结点树的根结点一定是0 00。以下只考虑n 1 n 1n1的情况。用d max ⁡ d_{\max}dmax​表示无向树中距离最远的两个结点之间的距离存在结点x xx和y yy的距离是d max ⁡ d_{\max}dmax​。用z zz表示从x xx到y yy的路径上的一个结点z zz可能和x xx或y yy重合将z zz到x xx和y yy的距离分别记为d x d_xdx​和d y d_ydy​则d x d y d max ⁡ d_x d_y d_{\max}dx​dy​dmax​以z zz为根结点的树的最小高度为max ⁡ ( d x , d y ) \max(d_x, d_y)max(dx​,dy​)理由如下。假设存在一个结点w ww和结点z zz的距离d w d_wdw​满足d w max ⁡ ( d x , d y ) d_w \max(d_x, d_y)dw​max(dx​,dy​)则d w d x d_w d_xdw​dx​和d w d y d_w d_ydw​dy​都大于d max ⁡ d_{\max}dmax​与无向树中距离最远的两个结点之间的距离是d max ⁡ d_{\max}dmax​矛盾。因此任意结点和结点z zz的距离都不超过max ⁡ ( d x , d y ) \max(d_x, d_y)max(dx​,dy​)以z zz为根结点的树的最小高度为max ⁡ ( d x , d y ) \max(d_x, d_y)max(dx​,dy​)。当∣ d x − d y ∣ ≤ 1 |d_x - d_y| \le 1∣dx​−dy​∣≤1时max ⁡ ( d x , d y ) ⌈ d max ⁡ 2 ⌉ \max(d_x, d_y) \Big\lceil \dfrac{d_{\max}}{2} \Big\rceilmax(dx​,dy​)⌈2dmax​​⌉此时以z zz为根结点的树的高度最小。由于同一条路径上满足∣ d x − d y ∣ ≤ 1 |d_x - d_y| \le 1∣dx​−dy​∣≤1的结点z zz有一个或两个因此对于任意无向树可以作为最小高度树的根结点的结点个数是一个或两个。为了寻找无向树中距离最远的两个结点之间的距离可以使用拓扑排序实现。由于题目中的图的表示方式是边数组为了方便处理需要首先将边数组转换成邻接结点列表的形式转换后可以在O ( 1 ) O(1)O(1)时间获得一个结点的全部相邻结点然后使用广度优先搜索遍历图。在无向图中拓扑排序时从度为1 11的结点开始使用广度优先搜索实现拓扑排序。首先将度为1 11的结点全部入队列此时队列中的结点为同一层的全部结点拓扑排序的过程中需要确保每一轮遍历的是同一层的全部结点。对于同一层的全部结点每次将一个结点出队列执行如下操作。得到该结点的所有相邻结点。对于每个相邻结点将相邻结点的出度减1 11。如果在更新出度之后相邻结点的出度变为1 11则将该相邻结点入队列。同一层的全部结点遍历结束之后队列中的结点为同一层的全部结点。上述做法可以确保每一轮遍历的是同一层的全部结点。拓扑排序的过程中每一轮都会遍历尚未遍历的最外层的全部结点。当尚未遍历的结点数不超过2 22时尚未遍历的结点是离所有最外层结点最远的结点因此尚未遍历的结点是所有的最小高度树的根结点。代码classSolution{publicListIntegerfindMinHeightTrees(intn,int[][]edges){ListIntegerrootsnewArrayListInteger();if(n1){roots.add(0);returnroots;}ListInteger[]adjacentArrnewList[n];for(inti0;in;i){adjacentArr[i]newArrayListInteger();}for(int[]edge:edges){adjacentArr[edge[0]].add(edge[1]);adjacentArr[edge[1]].add(edge[0]);}int[]degreesnewint[n];QueueIntegerqueuenewArrayDequeInteger();for(inti0;in;i){degrees[i]adjacentArr[i].size();if(degrees[i]1){queue.offer(i);}}intremainn;while(remain2){intsizequeue.size();for(inti0;isize;i){intnodequeue.poll();ListIntegeradjacentadjacentArr[node];for(intnext:adjacent){if(degrees[next]1){continue;}degrees[next]--;if(degrees[next]1){queue.offer(next);}}}remain-size;}while(!queue.isEmpty()){roots.add(queue.poll());}returnroots;}}复杂度分析时间复杂度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)其中n nn是树中的结点数。邻接结点列表和队列需要O ( n ) O(n)O(n)的空间。