minimum-height-trees

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

A tree is an undirected graph in which any two vertices are connected by&nbsp;exactly&nbsp;one path. In other words, any connected graph without simple cycles is a tree.

Given a tree of <code>n</code> nodes&nbsp;labelled from <code>0</code> to <code>n - 1</code>, and an array of&nbsp;<code>n - 1</code>&nbsp;<code>edges</code> where <code>edges[i] = [ai, bi]</code> indicates that there is an undirected edge between the two nodes&nbsp;<code>ai</code> and&nbsp;<code>bi</code> in the tree,&nbsp;you can choose any node of the tree as the root. When you select a node <code>x</code> as the root, the result tree has height <code>h</code>. Among all possible rooted trees, those with minimum height (i.e. <code>min(h)</code>)&nbsp; are called minimum height trees (MHTs).

Return a list of all MHTs&#39; root labels.&nbsp;You can return the answer in any order.

The height of a rooted tree is the number of edges on the longest downward path between the root and a leaf.

&nbsp;
Example 1:
<img alt="" src="https://assets.leetcode.com/uploads/2020/09/01/e1.jpg" style="width: 800px; height: 213px;" />
<pre>
Input: n = 4, edges = [[1,0],[1,2],[1,3]]
Output: [1]
Explanation: As shown, the height of the tree is 1 when the root is the node with label 1 which is the only MHT.
</pre>

Example 2:
<img alt="" src="https://assets.leetcode.com/uploads/2020/09/01/e2.jpg" style="width: 800px; height: 321px;" />
<pre>
Input: n = 6, edges = [[3,0],[3,1],[3,2],[3,4],[5,4]]
Output: [3,4]
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= n &lt;= 2 * 104</code></li>
	<li><code>edges.length == n - 1</code></li>
	<li><code>0 &lt;= ai, bi &lt; n</code></li>
	<li><code>ai != bi</code></li>
	<li>All the pairs <code>(ai, bi)</code> are distinct.</li>
	<li>The given input is guaranteed to be a tree and there will be no repeated edges.</li>
</ul>

findMinHeightTrees

Minimum Height Trees

Course Schedule

course-schedule

课程表

Course Schedule II

course-schedule-ii

课程表 II

Collect Coins in a Tree

collect-coins-in-a-tree

收集树中金币

Count Pairs of Connectable Servers in a Weighted Tree Network

count-pairs-of-connectable-servers-in-a-weighted-tree-network

在带权树网络中统计可连接服务器对数目

Find Minimum Diameter After Merging Two Trees

find-minimum-diameter-after-merging-two-trees

合并两棵树后的最小直径

Depth-First Search

Breadth-First Search

Graph

Topological Sort

树是一个无向图，其中任何两个顶点只通过一条路径连接。 换句话说，任何一个没有简单环路的连通图都是一棵树。

给你一棵包含&nbsp;<code>n</code>&nbsp;个节点的树，标记为&nbsp;<code>0</code>&nbsp;到&nbsp;<code>n - 1</code> 。给定数字&nbsp;<code>n</code>&nbsp;和一个有 <code>n - 1</code> 条无向边的 <code>edges</code>&nbsp;列表（每一个边都是一对标签），其中 <code>edges[i] = [ai, bi]</code> 表示树中节点 <code>ai</code> 和 <code>bi</code> 之间存在一条无向边。

可选择树中任何一个节点作为根。当选择节点 <code>x</code> 作为根节点时，设结果树的高度为 <code>h</code> 。在所有可能的树中，具有最小高度的树（即，<code>min(h)</code>）被称为 最小高度树 。

请你找到所有的 最小高度树 并按 任意顺序 返回它们的根节点标签列表。
树的 高度 是指根节点和叶子节点之间最长向下路径上边的数量。

&nbsp;

示例 1：
<img alt="" src="https://assets.leetcode.com/uploads/2020/09/01/e1.jpg" style="height: 213px; width: 800px;" />
<pre>
输入：n = 4, edges = [[1,0],[1,2],[1,3]]
输出：[1]
解释：如图所示，当根是标签为 1 的节点时，树的高度是 1 ，这是唯一的最小高度树。</pre>

示例 2：
<img alt="" src="https://assets.leetcode.com/uploads/2020/09/01/e2.jpg" style="height: 321px; width: 800px;" />
<pre>
输入：n = 6, edges = [[3,0],[3,1],[3,2],[3,4],[5,4]]
输出：[3,4]
</pre>

&nbsp;

<ul>
</ul>

提示：

<ul>
	<li><code>1 &lt;= n &lt;= 2 * 104</code></li>
	<li><code>edges.length == n - 1</code></li>
	<li><code>0 &lt;= ai, bi &lt; n</code></li>
	<li><code>ai != bi</code></li>
	<li>所有 <code>(ai, bi)</code> 互不相同</li>
	<li>给定的输入 保证 是一棵树，并且 不会有重复的边</li>
</ul>