列表

详情

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]

 

提示：

相似题目

课程表

课程表 II

原站题解

去查看

上次编辑到这里，代码来自缓存 点击恢复默认模板
class Solution { public: vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) { } };

typescript 解法, 执行用时: 134 ms, 内存消耗: 70.4 MB, 提交时间: 2024-03-17 23:34:32 

function findMinHeightTrees(n: number, edges: number[][]): number[] {
    if (n === 1) {
        return [0];
    }
    const g: number[][] = Array.from({ length: n }, () => []);
    const degree: number[] = Array(n).fill(0);
    for (const [a, b] of edges) {
        g[a].push(b);
        g[b].push(a);
        ++degree[a];
        ++degree[b];
    }
    const q: number[] = [];
    for (let i = 0; i < n; ++i) {
        if (degree[i] === 1) {
            q.push(i);
        }
    }
    const ans: number[] = [];
    while (q.length > 0) {
        ans.length = 0;
        const t: number[] = [];
        for (const a of q) {
            ans.push(a);
            for (const b of g[a]) {
                if (--degree[b] === 1) {
                    t.push(b);
                }
            }
        }
        q.splice(0, q.length, ...t);
    }
    return ans;
}

python3 解法, 执行用时: 100 ms, 内存消耗: 23.6 MB, 提交时间: 2023-06-11 09:16:48 

class Solution:
    def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:
        if n == 1:
            return [0]

        g = [[] for _ in range(n)]
        deg = [0] * n
        for x, y in edges:
            g[x].append(y)
            g[y].append(x)
            deg[x] += 1
            deg[y] += 1

        q = [i for i, d in enumerate(deg) if d == 1]
        remainNodes = n
        while remainNodes > 2:
            remainNodes -= len(q)
            tmp = q
            q = []
            for x in tmp:
                for y in g[x]:
                    deg[y] -= 1
                    if deg[y] == 1:
                        q.append(y)
        return q

golang 解法, 执行用时: 68 ms, 内存消耗: 10.1 MB, 提交时间: 2023-06-11 09:16:14 

func findMinHeightTrees(n int, edges [][]int) (nodes []int) {
    in, connect := make([]int, n), map[int][]int{}
    for _, edge := range edges {
        a, b := edge[0], edge[1]
        in[a]++
        in[b]++
        connect[a] = append(connect[a], b)
        connect[b] = append(connect[b], a)
    }
    for i := 0; i < n; i++ {
        if in[i] < 2 {
            nodes = append(nodes, i)
        }
    }
    for n > 2 {
        s := len(nodes)
        n -= s
        for _, node := range nodes {
            for _, other := range connect[node] {
                in[other]--
                if in[other] == 1 {
                    nodes = append(nodes, other)
                }
            }
        }
        nodes = nodes[s:]
    }
    return nodes
}

javascript 解法, 执行用时: 136 ms, 内存消耗: 63.1 MB, 提交时间: 2023-06-11 09:16:01 

/**
 * @param {number} n
 * @param {number[][]} edges
 * @return {number[]}
 */
var findMinHeightTrees = function(n, edges) {
    const degree = new Array(n).fill(0), connect = new Map()
    for(const edge of edges) {
        const a = edge[0], b = edge[1]
        degree[a]++
        degree[b]++
        var l0, l1
        if(connect.has(a))
            l0 = connect.get(a)
        else
            l0 = new Array()
        l0.push(b)
        connect.set(a, l0)
        if(connect.has(b))
            l1 = connect.get(b)
        else
            l1 = new Array()
        l1.push(a)
        connect.set(b, l1)
    }
    let nodes = new Array()
    for(let i = 0; i < n; i++)
        if(degree[i] < 2)
            nodes.push(i)
    while(n > 2) {
        n -= nodes.length
        const nxt = new Array()
        for(const node of nodes) {
            for(const other of connect.get(node)) {
                degree[other]--
                if(degree[other] == 1)
                    nxt.push(other)
            }
        }
        nodes = nxt
    }
    return nodes
};

java 解法, 执行用时: 23 ms, 内存消耗: 53.8 MB, 提交时间: 2023-06-11 09:15:45 

class Solution {
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        int[] in = new int[n];
        Map<Integer, List<Integer>> connect = new HashMap<>();
        for(int[] edge: edges) {
            in[edge[0]]++;
            in[edge[1]]++;
            List<Integer> l0 = connect.getOrDefault(edge[0], new ArrayList<>());
            l0.add(edge[1]);
            connect.put(edge[0], l0);
            List<Integer> l1 = connect.getOrDefault(edge[1], new ArrayList<>());
            l1.add(edge[0]);
            connect.put(edge[1], l1);
        }
        List<Integer> nodes = new ArrayList<>();
        for(int i = 0; i < n; i++)
            if(in[i] < 2)
                nodes.add(i);
        while(n > 2) {
            n -= nodes.size();
            List<Integer> nxt = new ArrayList<>();
            for(int node: nodes) {
                for(int other: connect.get(node)) {
                    in[other]--;
                    if(in[other] == 1)
                        nxt.add(other);
                }
            }
            nodes = nxt;
        }
        return nodes;
    }
}

python3 解法, 执行用时: 100 ms, 内存消耗: 24.2 MB, 提交时间: 2023-06-11 09:15:31 

# 拓扑 + bfs
class Solution:
    def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:
        in_degree, connect = [0] * n, defaultdict(list)
        for a, b in edges:
            in_degree[a] += 1
            in_degree[b] += 1
            connect[a].append(b)
            connect[b].append(a)
        nodes = [i for i, v in enumerate(in_degree) if v <= 1]
        while n > 2:
            n -= len(nodes)
            nxt = []
            for node in nodes:
                for other in connect[node]:
                    in_degree[other] -= 1
                    if in_degree[other] == 1:
                        nxt.append(other)
            nodes = nxt
        return nodes

上一题

© 2024 leetcode.cn