FilesExpand file tree

 master

/

MinimumHeightTrees.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

42 lines (40 loc) · 1.23 KB

 master

/

MinimumHeightTrees.java

Copy path

Top

File metadata and controls

• Code
• Blame

42 lines (40 loc) · 1.23 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

41

42

import java.util.*;

/**

* 从叶子节点开始，一层层剥掉，直到最后剩下的节点就是所求深度最大的

* https://discuss.leetcode.com/topic/30572/share-some-thoughts

*/

public class MinimumHeightTrees {

public List<Integer> findMinHeightTrees(int n, int[][] edges) {

if (n == 1) {

return Arrays.asList(0);

}

Set<Integer>[] sets = new HashSet[n];

for (int i = 0; i < n; i++) {

sets[i] = new HashSet<>();

}

for (int[] edge : edges) {

sets[edge[0]].add(edge[1]);

sets[edge[1]].add(edge[0]);

}

List<Integer> leaves = new LinkedList<>();

for (int i = 0; i < n; i++) {

if (sets[i].size() == 1) {

leaves.add(i);

}

}

while (n > 2) {

n -= leaves.size();

List<Integer> newLeaves = new LinkedList<>();

for (Integer k : leaves) {

int m = sets[k].iterator().next();

sets[k].clear();

sets[m].remove(k);

if (sets[m].size() == 1) {

newLeaves.add(m);

}

}

leaves = newLeaves;

}

return leaves;

}

}