> For the complete documentation index, see [llms.txt](https://emmaguo100.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://emmaguo100.gitbook.io/leetcode/08-01-2022-310.-minimum-height-trees.md).

# 08/01/2022  310. Minimum Height Trees

Noted:

DAG (有向图) Topological order based on the indegree = 0

NDAG (无向图) Topological order based on the degree = 1

For the tree-alike graph, the number of centroids is no more than 2.

we *trim* out the leaf nodes layer by layer, until we reach the *core* of the graph, which are the centroids nodes.

Method: for this question, the key point is to konw about the tree-like graph, the number of centroids is no more than 2.  Then we can use bfs to trim the leave node layer by layer. Here we use degree array to get the degree of each node. If the node's degree is 1, which is the leave node. We add them into the queue. Then we poll the node and iterate their neighbours and decrement their degree. After that, if their degrees are also 1, we add it to the queue. Repeat the process until the number of remaining node is 2. Finally add the node left inside the queue to the result list.

Time O(V)

Space O(V)