curTain

  1. 最小高度树

310. 最小高度树

对于一个具有树特征的无向图,我们可选择任何一个节点作为根。图因此可以成为树,在所有可能的树中,具有最小高度的树被称为最小高度树。给出这样的一个图,写出一个函数找到所有的最小高度树并返回他们的根节点。

格式

该图包含 n 个节点,标记为 0 到 n - 1。给定数字 n 和一个无向边 edges 列表(每一个边都是一对标签)。

你可以假设没有重复的边会出现在 edges 中。由于所有的边都是无向边, [0, 1]和 [1, 0] 是相同的,因此不会同时出现在 edges 里。

示例 1:

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

        0
        |
        1
       / \
      2   3 

输出: [1]
示例 2:

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

     0  1  2
      \ | /
        3
        |
        4
        |
        5 

输出: [3, 4]

解题思路

  1. 使用邻接表存储树的节点
  2. 使用一个数组保存入度为以的节点
  3. 依次互相消除值
  4. 遍历数组,返回最后结果

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/**
* @param {number} n
* @param {number[][]} edges
* @return {number[]}
*/
var findMinHeightTrees = function(n, edges) {
// 存储树
let graph = Array.from({ length: n }, ()=>([]))
for( let item of edges ){
graph[item[0]].push( item[1] )
graph[item[1]].push( item[0] )
}

// 入度为 1 的节点
let oneArr = Array.from({ length: n }, ()=>(false))

while( n > 2 ){
// 取出入度为 1 的节点
for( let item in graph ){
if( graph[item].length === 1 ){
oneArr[item] = true
}
}
// 遍历入度为 1 的节点
for( let i in graph ){
if( oneArr[i] && graph[i].length ){
// 互相删除节点
let otherPoint = graph[i].pop()
graph[otherPoint] = graph[otherPoint].filter( aa => aa != i )
n --
}
}
}
// 取出结果
let res = []
for( let i in oneArr ){
if( !oneArr[i] ) res.push(i)
}
return res
};

 评论