LeetCode 310. 最小高度树

题目描述

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

给你一棵包含 n 个节点的树，标记为从 0 到 n - 1。给定数字 n 和一个有 n - 1 条无向边 edges 的列表（其中 edges[i] = [ai, bi] 表示树中节点 ai 和 bi 之间存在一条边），你可以选择树中任何一个节点作为根。当选择节点 x 作为根节点时，设结果树的高度为 h。在所有可能的根节点中，具有最小高度的树（即 min(h)）被称为最小高度树。

请你找到所有的最小高度树并按任意顺序返回它们的根节点标签列表。

示例 1:
输入: n = 4, edges = [[1,0],[1,2],[1,3]]
输出: [1]
解释: 如图所示，当根是标签为 1 的节点时，树的高度是 1，这是唯一的最小高度树。

示例 2:
输入: n = 6, edges = [[3,0],[3,1],[3,2],[3,4],[5,4]]
输出: [3,4]

解题过程循序渐进讲解

这个问题的核心是，对于一棵树，其“中心”节点（可以是一个或两个）作为根时，树的高度会最小。我们可以通过一种“层层剥离”叶子的方法，逐步逼近树的中心。

第一步：理解问题与直觉

1. 树的性质：题目给出的图是一棵树，意味着它连通且无环。有 n 个节点，n-1 条边。
2. 最小高度：我们需要找到一个（或多个）根节点，使得从它出发到最远叶子的距离（即高度）最小。
3. 关键直觉：想象一下，最小高度树的根实际上位于这棵树最长路径（直径）的中间。如果最长路径的节点数是奇数，那么中心只有一个节点；如果是偶数，中心有两个节点。
4. 类比：这个过程类似于拓扑排序。我们从所有“叶子节点”（度数为1的节点）开始，一层一层地向内“剥离”。最后剩下的一个或两个节点，就是我们要找的中心，也就是最小高度树的根。

第二步：构建解题框架（拓扑排序思路）

1. 图的表示：首先，我们需要一种方式来存储这棵树（图）。邻接表是最佳选择，因为它能高效地表示稀疏图。
2. 度数组：我们需要一个数组来记录每个节点当前的度数（即与该节点相连的边的数量）。
3. 初始化：将所有度数为1的节点（叶子节点）加入一个队列中。
4. 层层剥离：
   • 在每一轮中，我们处理当前队列中的所有叶子节点。
   • 对于每个叶子节点，我们将其从图中“移除”（实际上是将其度数减为0，并标记为已处理）。
   • 同时，我们检查与这个叶子节点相邻的节点。将这些相邻节点的度数减1。
   • 如果某个相邻节点在减1后，度数变成了1，那么它就成了新的叶子节点，我们将其加入下一轮要处理的队列中。
5. 终止条件：我们持续这个过程，直到剩余的节点数不超过2个。为什么是2个？因为树的中心最多只能有两个节点。

第三步：详细步骤分解

假设 n = 6, edges = [[3,0],[3,1],[3,2],[3,4],[5,4]]。

1. 构建邻接表和度数组：

   • 邻接表 graph:
     • 0: [3]
     • 1: [3]
     • 2: [3]
     • 3: [0, 1, 2, 4]
     • 4: [3, 5]
     • 5: [4]
   • 度数组 degree: [1, 1, 1, 4, 2, 1]
     • （注意：在无向图中，度数是连接的边数）

2. 初始化队列：

   • 找到所有度数为1的节点：节点0、1、2、5。
   • 将它们加入队列。queue = [0, 1, 2, 5]
   • 剩余节点数 remainingNodes = 6。

3. 第一轮剥离：

   • 当前队列大小 size = 4。我们处理这4个节点。
   • 处理节点0：
     • 找到它的邻居：节点3。
     • 将节点3的度数从4减到3。degree[3] = 3。
     • 节点0被移除，remainingNodes 变为 5。
   • 处理节点1：
     • 邻居是节点3。
     • 节点3的度数从3减到2。degree[3] = 2。
     • remainingNodes = 4。
   • 处理节点2：
     • 邻居是节点3。
     • 节点3的度数从2减到1。degree[3] = 1。
     • remainingNodes = 3。
     • 注意：此时节点3的度数变成了1，但它不会被立即加入队列，因为我们要等本轮所有节点处理完再统一加入。
   • 处理节点5：
     • 邻居是节点4。
     • 节点4的度数从2减到1。degree[4] = 1。
     • remainingNodes = 2。
   • 第一轮结束。检查哪些节点的新度数变成了1：节点3和节点4。将它们加入新队列。newQueue = [3, 4]。
   • 现在 remainingNodes = 2，满足终止条件（<=2）吗？是的。所以算法可以停止了。

4. 返回结果：

   • 当前剩余的节点就是最小高度树的根，即 [3, 4]。

第四步：算法实现要点（伪代码）

def findMinHeightTrees(n, edges):
    if n == 1:
        return [0] # 只有一个节点，直接返回

    # 1. 构建图和度数组
    graph = [[] for _ in range(n)]
    degree = [0] * n

    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)
        degree[u] += 1
        degree[v] += 1

    # 2. 初始化队列，加入所有叶子节点（度=1）
    from collections import deque
    queue = deque()
    for i in range(n):
        if degree[i] == 1:
            queue.append(i)

    # 3. 层层剥离，直到剩余节点数 <= 2
    remainingNodes = n
    while remainingNodes > 2:
        # 记录当前层有多少叶子
        size = len(queue)
        # 一次性处理完当前层的所有叶子
        for _ in range(size):
            leaf = queue.popleft()
            remainingNodes -= 1 # 移除这个叶子
            # 更新它的邻居
            for neighbor in graph[leaf]:
                degree[neighbor] -= 1 # 邻居度数减1
                # 如果邻居变成新的叶子，加入下一轮队列
                if degree[neighbor] == 1:
                    queue.append(neighbor)

    # 4. 队列中剩下的节点就是答案
    return list(queue)

第五步：复杂度分析

• 时间复杂度：O(n)。每个节点和每条边都只被处理一次。
• 空间复杂度：O(n)。用于存储邻接表和队列。

总结
这个算法的精妙之处在于利用了树的特性，通过从外向内（从叶子向中心）的“拓扑排序”方式，高效地找到了使得树高最小的根节点。它避免了为每个节点做一次BFS/DFS来计算高度的O(n²)暴力解法。