310.最小高度树

链接：310.最小高度树
难度：Medium
标签：深度优先搜索、广度优先搜索、图、拓扑排序
简介：请你找到所有的 最小高度树 并按 任意顺序 返回它们的根节点标签列表。

题解 1 - cpp

• 编辑时间：2022-03-14
• 执行用时：180ms
• 内存消耗：77.6MB
• 编程语言：cpp
• 解法介绍：从所有叶子节点开始遍历，由外到内。

class Solution {
   public:
    struct node {
        int idx, cnt;
        unordered_set<int> chilren;
    };
    vector<int> findMinHeightTrees(int n, vector<vector<int>> &edges) {
        if (n == 1) return vector(1, 0);
        vector<node> list(n);
        for (int i = 0; i < n; i++) {
            list[i].idx = i;
            list[i].cnt = 0;
        }
        for (auto &edge : edges) {
            int n1 = edge[0], n2 = edge[1];
            list[n1].cnt++;
            list[n2].cnt++;
            list[n1].chilren.insert(n2);
            list[n2].chilren.insert(n1);
        }
        queue<int> q;
        for (int i = 0; i < n; i++) {
            if (list[i].cnt == 1) q.push(i);
        }
        vector<int> ans;
        while (q.size()) {
            ans.clear();
            int size = q.size();
            for (int i = 0; i < size; i++) {
                int node = q.front();
                q.pop();
                ans.push_back(node);
                list[node].cnt--;
                for (auto &child : list[node].chilren) {
                    list[child].cnt--;
                    if (list[child].cnt == 1) q.push(child);
                }
            }
        }
        return ans;
    }
};

题解 2 - cpp

• 编辑时间：2022-04-06
• 执行用时：172ms
• 内存消耗：77.7MB
• 编程语言：cpp
• 解法介绍：从外向内遍历。

class Solution {
   public:
    struct node {
        int val, cnt;
        unordered_set<int> children;
    };
    vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
        if (n == 1) return {0};
        vector<node> list(n);
        for (int i = 0; i < n; i++) {
            list[i].val = i;
            list[i].cnt = 0;
        }
        for (auto& edge : edges) {
            int n0 = edge[0], n1 = edge[1];
            list[n0].children.insert(n1);
            list[n1].children.insert(n0);
            list[n0].cnt++;
            list[n1].cnt++;
        }
        queue<int> q;
        for (auto& node : list) {
            if (node.cnt == 1) q.push(node.val);
        }
        vector<int> ans;
        int size = q.size();
        while (q.size()) {
            int idx = q.front();
            ans.push_back(idx);
            q.pop();
            list[idx].cnt--;
            for (auto& child : list[idx].children) {
                if (--list[child].cnt != 1) continue;
                q.push(child);
            }
            if (--size == 0) {
                size = q.size();
                if (size) ans.clear();
            }
        }
        return ans;
    }
};

题解 3 - python

• 编辑时间：2024-03-17
• 执行用时：295ms
• 内存消耗：67.8MB
• 编程语言：python
• 解法介绍：dfs。

class Solution:
    def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:
        if n == 1: return [0]
        if n == 2: return [0, 1]
        nodes = [[] for _ in range(n)]
        for n1, n2 in edges:
            nodes[n1].append(n2)
            nodes[n2].append(n1)
        @cache
        def dfs(node: int, parent: int) -> int:
            return 1 + max(dfs(child, node) if child != parent else 0 for child in nodes[node])
        ans_val = inf
        ans_arr = []
        for node in range(n):
            if len(nodes[node]) == 1: continue
            res = dfs(node, -1)
            if res <= ans_val:
                if res < ans_val: ans_arr.clear()
                ans_val = res
                ans_arr.append(node)
        return ans_arr