LeetCode: 310. Minimum Height Trees

LeetCode: 310. Minimum Height Trees

题目描述

For an undirected graph with tree characteristics, we can choose any node as the root. The result graph is then a rooted tree. Among all possible rooted trees, those with minimum height are called minimum height trees (MHTs). Given such a graph, write a function to find all the MHTs and return a list of their root labels.

Format
The graph contains n nodes which are labeled from 0 to n - 1. You will be given the number n and a list of undirected edges (each edge is a pair of labels).

You can assume that no duplicate edges will appear in edges. Since all edges are undirected, [0, 1] is the same as [1, 0] and thus will not appear together in edges.

Example 1 :

Input: n = 4, edges = [[1, 0], [1, 2], [1, 3]]

        0
        |
        1
       / \
      2   3 

Output: [1]

Example 2 :

Input: n = 6, edges = [[0, 3], [1, 3], [2, 3], [4, 3], [5, 4]]

     0  1  2
      \ | /
        3
        |
        4
        |
        5 

Output: [3, 4]

Note:

• According to the definition of tree on Wikipedia: “a tree is an undirected graph in which any two vertices are connected by exactly one path. In other words, any connected graph without simple cycles is a tree.”
• The height of a rooted tree is the number of edges on the longest downward path between the root and a leaf.

解题思路

1. 记，度为 1 的节点为叶子节点。显而易见从叶子节点到叶子节点的距离一定大于它们之间的节点分别到两个叶子节点的距离。因此，
2. 当存在非叶子节点时，叶子节点一定不是 MHT 的根
3. 当仅存在叶子节点时，所有的叶子节点都可以是 MHT 的根
4. 综上，将原图的叶子节点一层一层的删除，直到满足 3 中的条件，剩下的所有的节点都可以是 MHT 的根

AC 代码

func countLeaves(degrees []int, nodes []int) (innerNodes []int, leaves []int) {
    for i := 0; i < len(nodes); i++ {
        if degrees[nodes[i]] == 1 {
            leaves = append(leaves, nodes[i])
        } else {
            innerNodes = append(innerNodes, nodes[i])
        }
    }
    
    return innerNodes, leaves
}

func findMinHeightTrees(n int, edges [][]int) []int {
    
    // 邻接矩阵: 每一行第一个值表示该行能到达的节点的总数
    adjMatrix := make([][]bool, n)
    for i := 0; i < n; i++ {
        adjMatrix[i] = make([]bool, n+1)
    }
    
    // 每个节点的度
    degrees := make([]int, n)
    for i := 0; i < len(edges); i++ {
        adjMatrix[edges[i][0]][edges[i][1]] = true
        adjMatrix[edges[i][1]][edges[i][0]] = true
        degrees[edges[i][0]]++
        degrees[edges[i][1]]++
    }
    
    
    var nodes []int
    for i := 0; i < n; i++ {
        nodes = append(nodes, i)
    }
    for {
        innerNodes, leaves := countLeaves(degrees, nodes)
        if len(innerNodes) == len(nodes) { 
            break 
        } else if len(innerNodes) == 0 {
            nodes = leaves
            break
        }

        for i := 0; i < len(leaves); i++ {
            for j := 0; j < len(adjMatrix[leaves[i]]); j++ {
                // 找到叶子唯一的那个度，并删除它
                if adjMatrix[leaves[i]][j] {
                    adjMatrix[leaves[i]][j] = false
                    adjMatrix[j][leaves[i]] = false
                    degrees[leaves[i]]--
                    degrees[j]--
                    break
                }
            }
        }
    
        nodes = innerNodes
    }
    
    return nodes
}