Minimum Height Trees（最小高度树）

题目 / Problem

中文： 树是一种无向图，其中任意两个顶点之间恰好存在一条路径。换句话说，树是一个连通且没有简单环的图。

给定一棵包含 n 个节点的树，节点编号为 0 到 n - 1。edges 包含 n - 1 条无向边，其中 edges[i] = [ai, bi] 表示节点 ai 和 bi 之间存在一条边。

可以选择任意节点作为根。以某个节点为根时，树的高度是从根到最远叶子节点的路径边数。返回所有能够使树高最小的根节点编号，答案顺序不限。

English: A tree is an undirected graph in which any two vertices are connected by exactly one path—a connected graph without simple cycles.

Given a tree with n nodes labeled from 0 to n - 1 and n - 1 undirected edges, any node may be selected as the root. The tree's height is the number of edges on the longest downward path from the root to a leaf.

Return all root labels that produce the minimum possible height. The answer may be returned in any order.

示例 / Examples

Example 1

Input:  n = 4, edges = [[1,0],[1,2],[1,3]]
Output: [1]

分别选择节点 0、1、2、3 作为根的树高对比 / Height comparison when rooting the tree at nodes 0, 1, 2, and 3

只有以节点 1 为根时树高为 1，其他根节点都会产生高度为 2 的树。
Only node 1 produces a tree of height 1; every other root produces height 2.

Example 2

Input:  n = 6, edges = [[3,0],[3,1],[3,2],[3,4],[5,4]]
Output: [3,4]

节点 3 和 4 都能作为最小高度树的根 / Nodes 3 and 4 are both minimum-height tree roots

以节点 3 或 4 为根时，树的高度都为 2。
Rooting the tree at either node 3 or node 4 gives height 2.

约束 / Constraints

1 <= n <= 2 × 10^4
edges.length === n - 1
0 <= ai, bi < n
ai !== bi
所有边互不相同。
All edge pairs are distinct.
输入保证是一棵树，不存在重复边。
The input is guaranteed to be a tree with no repeated edges.

核心观察：答案是树的中心 / Key Observation: Tree Centers

如果选择靠近树边缘的节点作为根，到另一侧最远叶子的距离通常很长。为了最小化最大距离，根节点应该位于树的中心。
Choosing a root near the edge of a tree usually creates a long path to a leaf on the opposite side. To minimize the maximum distance, the root must lie at the center of the tree.

一棵树的中心最多只有两个：
A tree has at most two centers:

最长路径包含偶数条边时，只有一个中心节点。
If the longest path has an even number of edges, there is one center.
最长路径包含奇数条边时，有两个相邻的中心节点。
If the longest path has an odd number of edges, there are two adjacent centers.

因此最终答案只可能包含一个或两个节点。
Therefore, the answer contains only one or two nodes.

解题思路：逐层删除叶子 / Approach: Trim Leaves Layer by Layer

度数为 1 的节点是叶子节点。可以像剥洋葱一样，同时删除树最外层的所有叶子：
Nodes with degree 1 are leaves. Remove all outermost leaves simultaneously, like peeling layers from an onion:

外层叶子 / Outer leaves
        ↓ 删除 / remove
新的外层叶子 / New leaves
        ↓ 删除 / remove
树的中心 / Tree center(s)

每删除一层，所有剩余节点到原始边缘的距离都增加一层。最后剩下的一个或两个节点就是树的中心，也就是所有最小高度树的根。
Each removed layer moves one step inward from the original boundary. The final one or two remaining nodes are the tree centers and therefore all minimum-height roots.

这种过程类似无向图上的拓扑排序：
This process resembles topological sorting on an undirected graph:

建立邻接表和每个节点的度数。
Build an adjacency list and the degree of every node.
将所有度数为 1 的节点作为第一层叶子。
Collect all degree-1 nodes as the first leaf layer.
当剩余节点数大于 2 时，删除当前整层叶子。
While more than two nodes remain, remove the entire current leaf layer.
对每个被删除叶子的邻居执行 degree[neighbor]--。
Decrement the degree of every removed leaf's neighbor.
当邻居度数变为 1 时，它成为下一层叶子。
When a neighbor's degree becomes 1, it becomes a leaf in the next layer.

为什么必须同时删除一层？ / Why Remove a Whole Layer Together?

同一层叶子与树中心的距离相同。如果删除一个叶子后立即继续深入，而没有先处理其他叶子，就会破坏按距离分层的过程。
Leaves in the same layer have equal distance from the tree center. Removing one leaf and immediately going deeper before processing the others would break the distance-layer ordering.

因此每一轮要先固定当前 leaves，处理完全部叶子后再切换到 nextLeaves。
Each round must process the entire current leaves array before switching to nextLeaves.

JavaScript 实现 / JavaScript Implementation

/**
 * @param {number} n
 * @param {number[][]} edges
 * @return {number[]}
 */
function findMinHeightTrees(n, edges) {
  if (n === 1) {
    return [0];
  }

  const graph = Array.from({ length: n }, () => []);
  const degree = new Array(n).fill(0);

  for (const [first, second] of edges) {
    graph[first].push(second);
    graph[second].push(first);
    degree[first]++;
    degree[second]++;
  }

  let leaves = [];

  for (let node = 0; node < n; node++) {
    if (degree[node] === 1) {
      leaves.push(node);
    }
  }

  let remainingNodes = n;

  while (remainingNodes > 2) {
    remainingNodes -= leaves.length;
    const nextLeaves = [];

    for (const leaf of leaves) {
      for (const neighbor of graph[leaf]) {
        degree[neighbor]--;

        if (degree[neighbor] === 1) {
          nextLeaves.push(neighbor);
        }
      }
    }

    leaves = nextLeaves;
  }

  return leaves;
}

执行过程 / Walkthrough

使用 Example 2：
Using Example 2:

edges = [[3,0],[3,1],[3,2],[3,4],[5,4]]

初始度数：
Initial degrees:

节点 / Node	0	1	2	3	4	5
度数 / Degree	1	1	1	4	2	1

第一层叶子为：
The first leaf layer is:

[0,1,2,5]

删除它们后：
After removing them:

节点 3 的度数从 4 变为 1。
Node 3 decreases from degree 4 to 1.
节点 4 的度数从 2 变为 1。
Node 4 decreases from degree 2 to 1.

只剩两个节点：
Only two nodes remain:

[3,4]

因此它们都是最小高度树的根。
Therefore, both are minimum-height tree roots.

时间复杂度 / Time: O(n)，每个节点成为叶子至多一次，每条边只被处理常数次。
Every node becomes a leaf at most once, and every edge is processed only a constant number of times.
空间复杂度 / Space: O(n)，用于邻接表、度数数组和叶子数组。
O(n) for the adjacency list, degree array, and leaf arrays.

易错点 / Common Pitfalls

n === 1 时没有边，唯一答案是 [0]，必须单独处理。
When n === 1, there are no edges and the only answer is [0]; handle it separately.
这是无向图，建立邻接表时必须同时添加两个方向。
The graph is undirected, so add both directions to the adjacency list.
初始叶子是度数为 1 的节点，不是度数为 0 的节点。
Initial leaves have degree 1, not degree 0.
每轮必须同时删除当前所有叶子，再处理下一层。
Remove every leaf in the current layer before processing the next layer.
循环条件应为 remainingNodes > 2，因为树的中心可能有两个。
Use remainingNodes > 2 because a tree may have two centers.
最终答案最多包含两个节点，不需要对结果进行额外排序。
The final answer contains at most two nodes and does not require sorting.

Minimum Height Trees