Medium

题目描述

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

给你一棵包含 n 个节点的树，节点标记为 0 到 n - 1。给你一个数组 edges，其中 edges[i] = [ai, bi] 表示树中节点 ai 和 bi 之间有一条无向边。

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

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

树的高度是指根节点和叶子节点之间最长向下路径上边的数量。

示例 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 <= 2 * 10^4
  • edges.length == n - 1
  • 0 <= ai, bi < n
  • ai != bi
  • 所有 (ai, bi) 互不相同
  • 给定的输入保证是一棵树，不会有重复的边

解题思路

解题思路

这道题要求找到能使树高度最小的根节点。关键观察是：最小高度树的根节点一定位于树的"中心"位置。

核心思想

  • 树的直径（最长路径）的中点就是最优根节点
  • 最多只会有1个或2个这样的中心节点
  • 可以通过"拓扑排序 + BFS"的思想来找到中心

算法步骤

  1. 特殊情况处理：如果只有1-2个节点，直接返回
  2. 构建邻接表：记录每个节点的邻居
  3. 初始化叶子节点：度数为1的节点就是叶子
  4. 逐层剥离叶子：
    • 移除当前所有叶子节点
    • 更新剩余节点的度数
    • 找出新的叶子节点
    • 重复直到剩余节点数 ≤ 2
  5. 返回最后剩余的节点：这些就是最小高度树的根

为什么这样做？

想象不断剥掉树的外层叶子，最后剩下的1-2个节点就是树的"重心"，以它们为根的树高度最小。这类似于找树的直径的中点。

时间复杂度O(n)，空间复杂度O(n)，是最优解法。

代码实现

class Solution {
public:
    vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
        if (n <= 2) {
            vector<int> result;
            for (int i = 0; i < n; i++) {
                result.push_back(i);
            }
            return result;
        }
        
        // 构建邻接表
        vector<set<int>> graph(n);
        for (auto& edge : edges) {
            graph[edge[0]].insert(edge[1]);
            graph[edge[1]].insert(edge[0]);
        }
        
        // 找初始叶子节点
        queue<int> leaves;
        for (int i = 0; i < n; i++) {
            if (graph[i].size() == 1) {
                leaves.push(i);
            }
        }
        
        int remaining = n;
        
        // 逐层剥离叶子节点
        while (remaining > 2) {
            int leafCount = leaves.size();
            remaining -= leafCount;
            
            for (int i = 0; i < leafCount; i++) {
                int leaf = leaves.front();
                leaves.pop();
                
                // 移除叶子节点与其邻居的连接
                int neighbor = *graph[leaf].begin();
                graph[neighbor].erase(leaf);
                
                // 如果邻居变成了新的叶子节点
                if (graph[neighbor].size() == 1) {
                    leaves.push(neighbor);
                }
            }
        }
        
        vector<int> result;
        while (!leaves.empty()) {
            result.push_back(leaves.front());
            leaves.pop();
        }
        
        return result;
    }
};

class Solution:
    def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:
        if n <= 2:
            return list(range(n))
        
        # 构建邻接表
        graph = defaultdict(set)
        for a, b in edges:
            graph[a].add(b)
            graph[b].add(a)
        
        # 找初始叶子节点
        leaves = deque()
        for i in range(n):
            if len(graph[i]) == 1:
                leaves.append(i)
        
        remaining = n
        
        # 逐层剥离叶子节点
        while remaining > 2:
            leaf_count = len(leaves)
            remaining -= leaf_count
            
            for _ in range(leaf_count):
                leaf = leaves.popleft()
                
                # 移除叶子节点与其邻居的连接
                neighbor = graph[leaf].pop()
                graph[neighbor].remove(leaf)
                
                # 如果邻居变成了新的叶子节点
                if len(graph[neighbor]) == 1:
                    leaves.append(neighbor)
        
        return list(leaves)

public class Solution {
    public IList<int> FindMinHeightTrees(int n, int[][] edges) {
        if (n <= 2) {
            var result = new List<int>();
            for (int i = 0; i < n; i++) {
                result.Add(i);
            }
            return result;
        }
        
        // 构建邻接表
        var graph = new HashSet<int>[n];
        for (int i = 0; i < n; i++) {
            graph[i] = new HashSet<int>();
        }
        
        foreach (var edge in edges) {
            graph[edge[0]].Add(edge[1]);
            graph[edge[1]].Add(edge[0]);
        }
        
        // 找初始叶子节点
        var leaves = new Queue<int>();
        for (int i = 0; i < n; i++) {
            if (graph[i].Count == 1) {
                leaves.Enqueue(i);
            }
        }
        
        int remaining = n;
        
        // 逐层剥离叶子节点
        while (remaining > 2) {
            int leafCount = leaves.Count;
            remaining -= leafCount;
            
            for (int i = 0; i < leafCount; i++) {
                int leaf = leaves.Dequeue();
                
                // 移除叶子节点与其邻居的连接
                int neighbor = graph[leaf].First();
                graph[neighbor].Remove(leaf);
                
                // 如果邻居变成了新的叶子节点
                if (graph[neighbor].Count == 1) {
                    leaves.Enqueue(neighbor);
                }
            }
        }
        
        return leaves.ToList();
    }
}

var findMinHeightTrees = function(n, edges) {
    if (n === 1) return [0];
    
    const graph = Array.from({length: n}, () => new Set());
    const degree = new Array(n).fill(0);
    
    for (const [a, b] of edges) {
        graph[a].add(b);
        graph[b].add(a);
        degree[a]++;
        degree[b]++;
    }
    
    let queue = [];
    for (let i = 0; i < n; i++) {
        if (degree[i] === 1) {
            queue.push(i);
        }
    }
    
    let remaining = n;
    while (remaining > 2) {
        const size = queue.length;
        remaining -= size;
        const nextQueue = [];
        
        for (let i = 0; i < size; i++) {
            const leaf = queue[i];
            for (const neighbor of graph[leaf]) {
                degree[neighbor]--;
                if (degree[neighbor] === 1) {
                    nextQueue.push(neighbor);
                }
            }
        }
        queue = nextQueue;
    }
    
    return queue;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(n)每个节点和每条边都只被访问常数次
空间复杂度O(n)需要存储邻接表和队列

相关题目