diff options
Diffstat (limited to 'min_height_tree.py')
-rw-r--r-- | min_height_tree.py | 43 |
1 files changed, 43 insertions, 0 deletions
diff --git a/min_height_tree.py b/min_height_tree.py new file mode 100644 index 0000000..2f8c0b1 --- /dev/null +++ b/min_height_tree.py @@ -0,0 +1,43 @@ +# 310. Minimum Height Trees + +""" +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 tee. given a tree of 'n' nodes from 0 to 'n - 1' and an array of 'n - 1' +edges where 'edges[i] = [ai, bi]' indicates that there is an undirected edge +between the two nodes 'ai' and 'bi'in the the tree, you can choose any node +of the tree as the root. return a list of all mht's root labels. you can +return the answer in any order. +""" + + +class Solution(object): + def findMinHeightTrees(self, n, edges): + """ + :type n: int + :type edges: List[List[int]] + :rtype: List[int] + """ + if n == 1: + return [0] + adj = [set() for _ in range(n)] + for i, j in edges: + adj[i].add(j) + adj[j].add(i) + leaves = [i for i in range(n) if len(adj[i]) == 1] + while n > 2: + n -= len(leaves) + new_leaves = [] + for i in leaves: + j = adj[i].pop() + adj[j].remove(i) + if len(adj[j]) == 1: + new_leaves.append(j) + leaves = new_leaves + return leaves + + +if __name__ == "__main__": + obj = Solution() + print(obj.findMinHeightTrees(n=4, edges=[[1, 0], [1, 2], [1, 3]])) + print(obj.findMinHeightTrees(n=6, edges=[[3, 0], [3, 1], [3, 2], [3, 4], [5, 4]])) |