图：310.最小高度数， 题解

310. 最小高度树 - 力扣（LeetCode）

参考题解：

算法逻辑：算法的核心思路是逐层剪去叶子节点，直到剩下的节点是最小高度树的根。

示例：

假设有如下的树结构：

    0
   / \
  1   2
     / \
    3   4

初始时，叶子节点是1、3和4，剪掉这些叶子节点后，树变成：

    0
     \
      2

再次剪掉叶子节点2，最终剩下的节点是0，0就是最小高度树的根节点。

相同的边，还有一种最小高度数的情况是：

      2
   / \  \
  3   4 0
           \
            1

初始时剪掉叶子节点3，4，1；再次剪掉叶子节点0，最终剩下的节点是2，2就是最小高度数的根节点。

具体代码如下：

class Solution {
public:
    vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
        vector<int> res;
        // 如果只有一个节点，那么它就是最小高度树
        if (n == 1) {
            res.push_back(0);
            return res;
        }

        // 建立各个节点的出度表
        vector<int> degree(n, 0);
        // 建立图关系，在每个节点的列表中存储相连节点
        vector<vector<int>> map(n);
        for (const auto& edge : edges) {
            degree[edge[0]]++;
            degree[edge[1]]++; // 出度++
            map[edge[0]].push_back(edge[1]); // 添加相邻节点
            map[edge[1]].push_back(edge[0]);
        }

        // 建立队列
        queue<int> q;
        // 把所有出度为1的节点，也就是叶子节点入队
        for (int i = 0; i < n; ++i) {
            if (degree[i] == 1) {
                q.push(i);
            }
        }

        // 循环条件是队列不空
        while (!q.empty()) {
            res.clear(); // 每层循环都要new一个新的结果集合
            int size = q.size(); // 每一层的节点的数量
            for (int i = 0; i < size; ++i) {
                int cur = q.front();
                q.pop();
                res.push_back(cur); // 将当前节点加入结果集

                for (int neighbor : map[cur]) {
                    degree[neighbor]--;
                    if (degree[neighbor] == 1) {
                        q.push(neighbor); // 如果是叶子节点，入队
                    }
                }
            }
        }

        return res; // 返回最后一次保存的列表
    }
};